[백준 알고리즘][자바] 1011번 : Fly me to the Alpha Centauri

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

1011번: Fly me to the Alpha Centauri

안녕하세요. 이번 포스팅은 1011번 : Fly me to the Alpha Centauri입니다.
문제에 나오는 공간이동 장치는 다음과 같은 특징이 있습니다.

• 이전 작동 시기에 k광년을 이동하였으면 다음에는 k-1, k, k+1 광년만을 이동할 수 있습니다.

x지점에서 처음 출발 시에 이전 작동 시기가 0광년이기 때문에 이론상 1광년으로 출발하여 y지점까지 이동합니다.
단, 마지막 지점인 y지점 도착직전에는 반드시 1광년이여야합니다.

위의 조건에 따라 x지점에서 y지점까지 이동할 때, 필요한 최소한의 공간이동 장치 작동 횟수를 출력합니다.

예를 들어 x가 0 y가 5일 때,
0 -> 1 -> 3-> 4 -> 5 이렇게 총 4번 이동합니다.

따라서 거리별로 표를 만들어보면 아래와 같습니다.

거리(y-x)	패턴	이동 광년 수의 최대값(Max)	이동횟수
1	1	1	1
2	11	1	2
3	111	1	3
4	121	2	3
5	1211	2	4
6	1221	2	4
7	12211	2	5
8	12221	2	5
9	12321	3	5
10	123211	3	6
11	123221	3	6
12	123321	3	6
13	1233211	3	7
14	1233221	3	7
15	1233321	3	7

이 문제의 핵심은 공간이동 장치의 이동 광년 수의 최댓값입니다.
이동 광년 수의 최댓값이 변화하는 지점 즉 1, 4, 9, 16... 거리의 제곱근이 자연수일때 최대값이 한 자릿수가 올라갑니다.

• 거리가 4일 때 -> 최댓값 = 2, 이동 횟수 = 3
• 거리가 9일 때 -> 최댓값 = 3, 이동 횟수 = 5

최댓값이 변화하는 지점 거리의 제곱근이 자연수일 때 이동 횟수는 Max * 2 - 1입니다.

최댓값이 2와 3일때 나머지 이동 횟수는 아래와 같습니다.

• 최대값이 2일 때 -> 4가 2번, 5가 2번
• 최댓값이 3일 때 -> 6이 3번, 7이 3번

따라서 거리수가 1, 4, 9... 에서 최댓값만큼 이동 횟수가 반복됩니다.
이것을 수식으로 나타내면

• Max * Max < 거리 <= Max * Max + Max---> 이동 횟수 = Max * 2
• Max * Max + Max < 거리 ---> 이동 횟수 = Max * 2 + 1

위의 수식에서 Max * Max 가 제곱근이 자연수인 거리 1, 4, 9, 16 인 것입니다.

정리를 하자면 아래의 세 가지의 경우의 수에 따라 이동 횟수가 정해집니다.

1. 거리 = Max * Max 일 때, 이동 횟수 = Max * 2 - 1
2. Max * Max < 거리 <= Max * Max + Max 일때, 이동횟수 = Max * 2
3. Max * Max + Max < 거리 일때, 이동횟수 = Max * 2 + 1

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int T = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수 for(int i = 0 ; i < T ; i++) { String[] XY = br.readLine().split(" "); int x = Integer.parseInt(XY[0]); int y = Integer.parseInt(XY[1]); int distance = y - x; // 거리 int max = (int)Math.sqrt(distance); // 최대값(Max) if(distance == max * max) { // 1번 경우의 수 bw.write(String.valueOf(max * 2 - 1) + "\n"); }else if(distance > max * max && distance <= max * max + max) { // 2번 경우의 수 bw.write(String.valueOf(max * 2) + "\n"); }else { // 3번 경우의 수 bw.write(String.valueOf(max * 2 + 1) + "\n"); } } br.close(); bw.flush(); bw.close(); } }