[백준][Java] 1011번 Fly me to the Alpha Centauri

문제에서 움직이는 우주선의 특징을 이용하여

규칙을 찾아내야 합니다.

저 같은 경우는 연습장에 차근차근 써 봤습니다.

거리 1부터 7까지 최소한의 도약 횟수를 문제로 써보다보니

규칙 하나를 찾을 수 있었습니다.

x개의 자리를 가진 숫자의 MAX값의 집합에는 이러한 규칙이 있습니다.

1자리  1                   ->            null              1               null

2자리  1 1                ->             null             1 1              null

3자리  1 2 1             ->              null 1           2              1 null

4자리  1 2 2 1           ->              null 1          2 2            1 null

5자리  1 2 3 2 1        ->               null 1 2         3           2 1 null

6자리  1 2 3 3 2 1      ->               null 1 2        3 3         2 1 null

7자리  1 2 3 4 3 2 1    ->               null 1 2 3       4       3 2 1 null

....            ....

보시면 처음 시작을 0자리 (이해가 안가실지도 모르지만 null이 2개 있다고 생각하시면)

0자리에서 1자리로 갈 때 

null 1 null

기존의 자리 수 중앙에 숫자가 하나 들어갑니다. 그 다음 자리수 또한 숫자 1이 들어가

null 1 1 null

그 숫자가 쌍으로 2번 들어가면 이제 1이 늘어난 숫자인 2가 중앙에 들어가

null 1 2 1 null .. 이런 식의 규칙을 갖습니다.

즉 해당 자리수가 가질 수 있는 최대값의 규칙을 찾아, y부터 x사이의 거리값이 n자리와 n+1자리 

숫자의 사이에 위치하게 되면 문제에서 요구하는 우주선의 도약 횟수는 n+1이 되는 것 입니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); long[] a = new long[T]; long x=0,y=0; int[] res = new int[T]; for(int i=0; i<T; i++) { x=sc.nextLong(); y=sc.nextLong(); a[i]=y-x; } for(int i=0; i<T; i++) { long max=0,unit=1,unit_up=0; while(true) { max+=unit; res[i]++; unit_up++; if(max>=a[i]) break; else if(unit_up==2) { unit++; unit_up=0; } } } for (int i : res) { System.out.println(i); } } }