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

[문제 바로 가기] - Fly me to the Alpha Centauri

💡 접근 방식

이 문제의 알고리즘 분류가 수학인 이유가 있다.
직접 손으로 적어가며 규칙을 찾고 그걸 코드로 작성해야 한다.

distance	이동 거리	count	제곱근
1	1	1	1
2	11	2	1
3	111	3	1
4	121	3	2
5	1121	4	2
6	1221	4	2
7	11221	5	2
8	12221	5	2
9	12321	5	3
10	112321	6	3
11	122321	6	3
12	123321	6	3
13	1123321	7	3
14	1223321	7	3
15	1233321	7	3
16	1234321	7	4
17	11234321	8	4
18	12234321	8	4
19	12334321	8	4
20	12344321	8	4
...

이렇게 하나하나 적다보면 규칙이 보인다.

첫번째 접근

count의 수가 1부터 (1, 2), (33, 44), (555, 666)... 와 같이 2개씩 반복된다.
그래서 처음엔 distance가 어떤 범위에 해당하는지 구하려고 했지만 구현하는 데 (ㅜㅜ) 실패하고 다른 규칙을 찾았다.

두번째 접근

표를 보면 (제곱근) * (제곱근) + (제곱근)이 되는 수와 (제곱근) * (제곱근) 이 되는 수가 count의 경계값이 된다. (각각의 숫자에 같은 효과로 표시해두었다.)

1. (제곱근) * (제곱근) + (제곱근)보다 큰 수는 (제곱근) * 2 + 1만큼의 count를 가진다.
2. 그 외의 값들 중, (제곱근) * (제곱근)과 같은 수는 (제곱근) * 2 - 1의 count를 가진다.
3. 1, 2번에 해당되지 않는 수들은 (제곱근) * 2의 count를 가지게 된다.

이와 같은 순서로 코드를 작성했다.

이 문제는 정해진 답이 있다기보단 본인이 스스로 규칙을 찾아서 풀면 되는 것 같다!

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 백준 Fly me to the Alpha Centauri
 * - 수학
 */

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		
		for (int t = 0; t < T; t++) {
			int answer = 0;
			
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int distance = y - x;
			
			int squareRoot = (int) Math.sqrt(distance);
			if (distance > squareRoot * squareRoot + squareRoot) {
				answer = squareRoot * 2 + 1;
			} else {
				if (distance == squareRoot * squareRoot) {
					answer = squareRoot * 2 - 1;
				} else {
					answer = squareRoot * 2;
				}
			}
			
			System.out.println(answer);
		}
	}
}