알고리즘 풀이/백준

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

배게 2018. 4. 26. 19:34
728x90

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

규칙을 찾아내야 합니다.

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

거리 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);
		}	
	}
}


저작자표시