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

 

 

<코드>

import java.util.*;
public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		for (int i = 0; i < T; i++) {
			
			int x = sc.nextInt();
			int y = sc.nextInt();
			int s = y - x;
			int j = (int)Math.sqrt(s); 
			
			if(j*j == s) {
				System.out.println(2*j-1);
			}else if(j*j+j >= s){
				System.out.println(2*j);
			} else {
				System.out.println(2*j+1);
			}
		}

	}
}

 

풀이 방법

이동거리(s)	이동방법	작동횟수	제곱수
1	1	1	O
2	11	2
3	111	3
4	121	3	O
5	1211	4
6	1221	4
7	12211	5
8	12221	5
9	12321	5	O
10	123211	6
11	123221	6
12	123321	6
13	1233211	7
14	1233221	7
15	1233321	7
16	1234321	7	O
17	12343211	8
18	12343221	8
19	12343321	8
20	12344321	8
21	123443211	9
22	123443221	9
23	123443321	9
24	123444321	9
25	123454321	9	O
26	1234543211	10
27	1234543221	10
28	1234543321	10
29	1234544321	10
...	...	...	...

 

규칙을 살펴보게 되면 이동거리가 제곱수일 경우 

• 이동거리 1 => 작동횟수 1
• 이동거리 4 => 작동횟수 3
• 이동거리 9 => 작동횟수 5
• 이동거리 16 => 작동횟수 7
• 이동거리 25 => 작동횟수 9

입니다.

 

그리고 아래와 같은 규칙들을 발견할 수 있었습니다.

• 이동거리 1 => 작동횟수 1
  • 이동거리 2 => 작동횟수 2
  • 이동거리 3 => 작동횟수 3
• 이동거리 4 => 작동횟수 3
  • 이동거리 5 => 작동횟수 4
  • 이동거리 6 => 작동횟수 4
  • 이동거리 7 => 작동횟수 5
  • 이동거리 8 => 작동횟수 5
• 이동거리 9 => 작동횟수 5
  • 이동거리 10 => 작동횟수 6
  • 이동거리 11 => 작동횟수 6
  • 이동거리 12 => 작동횟수 6
  • 이동거리 13 => 작동횟수 7
  • 이동거리 14 => 작동횟수 7
  • 이동거리 15 => 작동횟수 7
• 이동거리 16 => 작동횟수 7
  • 이동거리 17 => 작동횟수 8
  • 이동거리 18 => 작동횟수 8
  • 이동거리 19 => 작동횟수 8
  • 이동거리 20 => 작동횟수 8
  • 이동거리 21 => 작동횟수 9
  • 이동거리 22 => 작동횟수 9
  • 이동거리 23 => 작동횟수 9
  • 이동거리 24 => 작동횟수 9
• 이동거리 25 => 작동횟수 9

 

따라서 거리 s를 가기 위한 최소한의 작동횟수를 찾는다면,

루트s를 통해 제곱수를 찾고 답을 구할 수 있게 됩니다.

 

https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri