𝝅번째 알파카의 개발 낙서장

screen

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

posts

알고리즘

시리즈 톺아보기

백준 알고리즘

백준 알고리즘
count

다리 놓기 🔗

랭크 사용 언어
image JAVA

🔗 전체 1011번 문제

조건 🔗

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

문제 🔗

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

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

image

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

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

입력 🔗

입력의 첫 줄에는 테스트케이스의 개수 가 주어진다. 각각의 테스트 케이스에 대해 현재 위치 와 목표 위치 가 정수로 주어지며, 는 항상 보다 작은 값을 갖는다.

출력 🔗

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

케이스 🔗

예제 1 🔗

  • 입력

TC

03
10 3
21 5
345 50
  • 출력

TC

03
13
24

풀이 🔗

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

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

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

  1. 처음, 끝 구간은 반드시 한 칸만 워프할 수 있다.
  2. 만큼 이동할 경우, ~ 만큼만 이동 가능
  3. 반드시 정확한 지점에 도착해야함 (통과 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

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

9의 경우 이므로 식이 성립함을 알 수 있다.

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

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

  • 보다 크면서 가장 가까운 제곱수
  • 가 속한 제곱수 구간의 중간값
  1. 에 제곱근 연산을 수행하고 이를 반올림한다. 보다 크면서 와 가장 가까운 제곱수의 제곱근 이 계산된다.
  2. 을 제곱하여 가장 근접한 제곱수 을 계산한다.
  3. 의 식으로 가 속한 제곱수 구간의 중간값을 계산한다.
  4. 일 경우, 의 가동 횟수와 동일한 식을 적용한다.
  5. 일 경우, 의 가동 횟수에서 1을 뺀 식을 적용한다.

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

이므로, 이를 반올림하면 3이 계산된다. 즉, 7보다 크면서 가장 가까운 제곱수는 다.

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

9의 가동횟수는 이므로 7의 가동 횟수 역시 5가 된다.

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

전체 소스 🔗

JAVA

0import java.io.BufferedReader;
1import java.io.IOException;
2import java.io.InputStreamReader;
3
4/**
5 * 백준 전체 1011 문제 알고리즘 클래스
6 *
7 * @author RWB
8 * @see <a href="https://blog.itcode.dev/posts/2021/06/11/a1011">1011 풀이</a>
9 * @since 2021.06.11 Fri 09:06:34
10 */
11public class Main
12{
13 /**
14 * 메인 함수
15 *
16 * @param args: [String[]] 매개변수
17 *
18 * @throws IOException 데이터 입출력 예외
19 */
20 public static void main(String[] args) throws IOException
21 {
22 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
23
24 // 케이스 수
25 int T = Integer.parseInt(reader.readLine());
26
27 for (int i = 0; i < T; i++)
28 {
29 String[] temp = reader.readLine().split(" ");
30
31 // 현재 위치
32 double x = Double.parseDouble(temp[0]);
33
34 // 목표 위치
35 double y = Double.parseDouble(temp[1]);
36
37 // x, y 사이의 거리
38 double distance = y - x;
39
40 System.out.println(solve(distance));
41 }
42
43 reader.close();
44 }
45
46 /**
47 * 가동횟수 반환 함수
48 *
49 * @param distance: [double] 거리
50 *
51 * @return [int] 가동횟수
52 */
53 private static int solve(double distance)
54 {
55 int result;
56
57 double ref = Math.sqrt(distance);
58
59 // 제곱수일 경우
60 if (ref % 1 == 0)
61 {
62 result = (int) (2 * ref - 1);
63 }
64
65 // 아닐 경우
66 else
67 {
68 double next = Math.ceil(ref);
69
70 // 이전 제곱수와 다음 제곱수의 중간보다 큰 수일 경우
71 if (distance > Math.pow(next, 2) - next)
72 {
73 result = (int) (2 * next - 1);
74 }
75
76 // 아닐 경우
77 else
78 {
79 result = (int) (2 * next - 2);
80 }
81 }
82
83 return result;
84 }
85}

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

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

분류 🔗

  • 수학