[백준 / JAVA] 백준 알고리즘 1011번 Fly me to the Alpha Centauri

⏰ 2021-06-11 (금) 14:14:09

시리즈 모아보기

백준 알고리즘

13 / 23

Table of Contents

1. 다리 놓기

1.1. 조건

1.2. 문제

1.3. 입력

1.4. 출력

1.5. 케이스

1.5.1. 예제 1

2. 풀이

2.1. 제곱수의 가동 횟수 일반식

2.2. 제곱수가 아닌 수의 가동 횟수 일반식

2.1. 전체 소스

2.2. 분류

다리 놓기

랭크	사용 언어
	JAVA

🔗 🔗 전체 1011번 문제

조건

시간제한	메모리 제한
2초	512MB

문제

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다.

그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다. 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는 단점이 있어서, 이전 작동시기에 $k$ 광년을 이동하였을 때는 $k - 1$ , $k$ 혹은 $k + 1$ 광년만을 다시 이동할 수 있다. 예를 들어, 이 장치를 처음 작동시킬 경우 -1 , 0 , 1 광년을 이론상 이동할 수 있으나 사실상 음수 혹은 0 거리만큼의 이동은 의미가 없으므로 1 광년을 이동할 수 있으며, 그 다음에는 0 , 1 , 2 광년을 이동할 수 있는 것이다. ( 여기서 다시 2광년을 이동한다면 다음 시기엔 1, 2, 3 광년을 이동할 수 있다)

김우현은 공간이동 장치 작동시의 에너지 소모가 크다는 점을 잘 알고 있기 때문에 $x$ 지점에서 $y$ 지점을 향해 최소한의 작동 횟수로 이동하려 한다. 하지만 $y$ 지점에 도착해서도 공간 이동장치의 안전성을 위하여 $y$ 지점에 도착하기 바로 직전의 이동거리는 반드시 1광년으로 하려 한다.

김우현을 위해 $x$ 지점부터 정확히 $y$ 지점으로 이동하는데 필요한 공간 이동 장치 작동 횟수의 최솟값을 구하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트케이스의 개수 $T$ 가 주어진다. 각각의 테스트 케이스에 대해 현재 위치 $x$ 와 목표 위치 $y$ 가 정수로 주어지며, $x$ 는 항상 $y$ 보다 작은 값을 갖는다. $(0 ≤ x < y < 2^31)$

출력

각 테스트 케이스에 대해 $x$ 지점으로부터 $y$ 지점까지 정확히 도달하는데 필요한 최소한의 공간이동 장치 작동 횟수를 출력한다.

케이스

예제 1

입력

출력

풀이

Frank Sinatra의 🔗 Fly me to the moon을 오마주한 제목인 거 같다.

시나트라를 Fallout NV의 Blue Moon으로 처음 접했었는데, 그 후에 Come fly with me나 Theme from Newyork Newyork 같이 좋은 곡들이 너무 많아서 자주 듣는 편이다.

문제로 돌아와서, 러프하게 보면 "무작정 빨리가면 되지 않나?"라고 생각할 수 있다. 하지만 아래 두 조건이 발목을 잡는다.

처음, 끝 구간은 반드시 한 칸만 워프할 수 있다.
$k$ 만큼 이동할 경우, $k - 1$ ~ $k + 1$ 만큼만 이동 가능함
반드시 정확한 지점에 도착해야함 (통과 X)

위 조건들 때문에 새벽 2시 강남의 "과학"마냥 쏘다니면 안 된다.

경우의 수는 아니고, 정해진 규칙이 있으니 이를 계산하여 순서대로 나열하면 단서를 발견할 수 있을 것 같다.

거리	내용	가동 횟수
1	1	1
2	1 1	2
3	1 1 1	3
4	1 2 1	3
5	1 2 1 1	4
6	1 2 2 1	4
7	1 2 2 1 1	5
8	1 2 2 2 1	5
9	1 2 3 2 1	5
10	1 2 3 2 1 1	6
11	1 2 3 2 2 1	6
12	1 2 3 3 2 1	6
13	1 2 3 3 2 1 1	7
14	1 2 3 3 2 2 1	7
15	1 2 3 3 3 2 1	7
16	1 2 3 4 3 2 1	7

잘 안 보일 수도 있으나, 규칙성 찾을 때 가장 만만한 제곱수(1, 4, 9...)를 기준으로 규칙을 정의할 수 있다. 특징은 아래와 같다.

제곱수 이후로 가동 횟수가 1 증가한다.
현재 제곱수와 다음 제곱수의 중간에서 가동 횟수가 1 증가한다.

즉, 제곱수 이후로 가시적인 변화가 있으며, 제곱수를 기준으로 구간의 중간에서 가동률이 1 증가한다.

제곱수의 가동 횟수 일반식

거리	내용	가동 횟수
1	1	1
4	1 2 1	3
9	1 2 3 2 1	5
16	1 2 3 4 3 2 1	7

제곱수의 가동률은 아래와 같다. 제곱수 $n$ 의 가동 횟수 일반식은 아래와 같다.

2\sqrt{n} - 1

9의 경우 $2 * 3 - 1 = 5$ 이므로 식이 성립함을 알 수 있다.

제곱수가 아닌 수의 가동 횟수 일반식

제곱수 사이의 중간에서 가동 횟수가 바뀌므로, 이 중간값을 계산하면 된다. 제곱수가 아닌 일반적인 숫자 $k$ 가 있다고 가정하자. 이 규칙은 제곱수를 중심으로 돌아가므로, $k$ 를 통해 제곱수를 구해야 한다. 구해야 할 요소는 아래와 같다.

$k$ 보다 크면서 가장 가까운 제곱수
$k$ 가 속한 제곱수 구간의 중간값

$k$ 에 제곱근 연산을 수행하고 이를 반올림한다. $k$ 보다 크면서 $k$ 와 가장 가까운 제곱수의 제곱근 $\sqrt{n}$ 이 계산된다.
$\sqrt{n}$ 을 제곱하여 가장 근접한 제곱수 $n$ 을 계산한다.
$n - \sqrt{n}$ 의 식으로 $k$ 가 속한 제곱수 구간의 중간값 $t$ 을 계산한다.
$k > t$ 일 경우, $n$ 의 가동 횟수와 동일한 $2\sqrt{n} - 1$ 식을 적용한다.
$k <= t$ 일 경우, $n$ 의 가동 횟수에서 1을 뺀 $2\sqrt{n} - 2$ 식을 적용한다.

위 방법을 토대로 7의 가동 횟수를 계산해보자.

$\sqrt{7} \fallingdotseq 2.646$ 이므로, 이를 반올림하면 3이 계산된다. 즉, 7보다 크면서 가장 가까운 제곱수는 $3^2 = 9$ 다.

$9 - \sqrt{9} = 9 - 3 = 6$ 이므로, $k$ 가 속한 제곱수 구간의 중간값은 6이다. 숫자가 6보다 클 경우 9와 가동 횟수가 동일하다. 주어진 숫자는 7이므로 9의 가동 횟수와 동일하다.

9의 가동횟수는 $2\sqrt{9} - 1 = 6 - 1 = 5$ 이므로 7의 가동 횟수 역시 5가 된다.

위 절차를 코드로 녹여내면 된다. 코드 구현 난이도는 낮다.

전체 소스

JAVA
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 백준 전체 1011 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/11/a1011">1011 풀이</a>
 * @since 2021.06.11 Fri 09:06:34
 */
public class Main
{
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		// 케이스 수
		int T = Integer.parseInt(reader.readLine());
		
		for (int i = 0; i < T; i++)
		{
			String[] temp = reader.readLine().split(" ");
			
			// 현재 위치
			double x = Double.parseDouble(temp[0]);
			
			// 목표 위치
			double y = Double.parseDouble(temp[1]);
			
			// x, y 사이의 거리
			double distance = y - x;
			
			System.out.println(solve(distance));
		}
		
		reader.close();
	}
	
	/**
	 * 가동횟수 반환 함수
	 *
	 * @param distance: [double] 거리
	 *
	 * @return [int] 가동횟수
	 */
	private static int solve(double distance)
	{
		int result;
		
		double ref = Math.sqrt(distance);
		
		// 제곱수일 경우
		if (ref % 1 == 0)
		{
			result = (int) (2 * ref - 1);
		}
		
		// 아닐 경우
		else
		{
			double next = Math.ceil(ref);
			
			// 이전 제곱수와 다음 제곱수의 중간보다 큰 수일 경우
			if (distance > Math.pow(next, 2) - next)
			{
				result = (int) (2 * next - 1);
			}
			
			// 아닐 경우
			else
			{
				result = (int) (2 * next - 2);
			}
		}
		
		return result;
	}
}

주의할 점이 하나 있는데, $x$ 와 $y$ 의 최대값이 $2^31$ 이다. int의 최대값은 2,147,483,647이지만, $2^31$ 은 2,147,483,648이므로 $x$ , $y$ 의 거리 계산 시 int를 사용하면 안 된다. 결과만 int형으로 출력해야 한다.

메모이제이션을 적용할까 했지만, 배열을 $2^31$ 크기만큼 초기화해야 하므로 오히려 오버헤드가 더 심하게 발생할 것 같다. 재귀함수도 아니니 메모이제이션을 적용해도 별차이 없을 것 같다.