[BOJ 1011번] Fly me to the Alpha Centauri

[BOJ 1011번]  Fly me to the Alpha Centauri

 

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

1011번: Fly me to the Alpha Centauri

 

 

이 문제는 이렇게 푸는 것이 확실한 것 같지만 더 이상 풀이에 진전이 없어서 해답을 본 문제이다.. 내가 생각한 풀이는 맞았으나 이를 코드로 구현하기가 꽤나 까다로웠던 문제였다. 

 

 

내가 생각한 풀이 - 1

시작 위치 x 목표위치 y가 어떻든 중요한건 이동해야 할 거리가 중요하다. 이에 따라서 이동방법이 달라지기 때문이다. 가령 시작위치 x : 1 목표위치 y: 11 인경우나 시작위치 1000001 목표위치 y: 1000011 가 최소로 이동하는 방법은 같다는 뜻이된다. 우선 이동해야 할 거리에 따라서 몇 번을 이동해야하며 어떻게 이동해야 하는지 살펴보자. 이렇게 풀이를 적다보면 해결책이 떠오르곤 한다.

 

이동거리	이동 방법	이동 횟수
1	1	1
2	11	2
3	111	3
4	121	3
5	1211	4
6	1221	4
7	12121	5
8	12221	5
9	12321	5
10	123211	6
11	123221	6
12	123321	6

 

위의 표는 이동거리에 따른  최소한의 공간이동 장치 작동 횟수이다.  또한 생각해 볼점은 0광년으로 간다는 것은 의미 없는 짓이다.  이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 있으므로 순차적인 수열이 구성이 될 것이다. 또한 최소로 이동해야 하기 때문에 가능하면 숫자가 커지는 것이 좋을 것이다. 또한 적당한 때에 속도를 줄여줘야 할 것이다. 이는 직전의 이동거리는 1광년이 되어야 하기 때문이다! 뭔가 이렇게 생각하면 풀릴것 같지만 진전이 없다.. 

 

 

풀이 참고

 

내가 접근한 풀이와 마찬가지로 이동거리에 따른 이동방법과 이동횟수를 쭉 나열한 풀이다.

 

이동거리	이동 방법	이동 횟수
1	1	1
2	11	2
3	111	3
4	121	3
5	1211	4
6	1221	4
7	12121	5
8	12221	5
9	12321	5
10	123211	6
11	123221	6
12	123321	6
13	1233211	7
14	1233221	7
15	1233321	7
16	1234321	7
17	12343211	8

 

여기서 주목해야 할 부분은 이동횟수가 바뀌는 부분이다.

 

• 이동거리가 제곱수인경우 최소이동횟수가 변한다. (빨간색 마킹)
• 이동방법이 대칭인 경우 최소이동횟수가 변한다.   (노란색 마킹)
• 교차해서 2가지가 나타난다. ( 제곱수 -> 대칭 -> 제곱수 -> 대칭 -> .... )

이 부분을 파악했다면 어렵지만 코드로 구현을 할 수 있다.

 

구현 - 1

import java.util.Scanner;
 
public class p1011{
    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 dist = y - x;
            System.out.println(solve(dist));
        }
    }
    public static long solve(int d) {
        long answer = 0;
        if(d <= 3) return d;
        for(long n = 1; ;n++) {
            if(n*(n-1) < d && d <= n*n) {
                answer = 2 * n - 1;
                break;
            }
            if(n*n < d && d <= n*(n+1)) {
                answer = 2*n;
                break;
            }
        }
        return answer;
    }
}