[백준 / BOJ] - 1011번 Fly me to the Alpha Centauri C++ 풀이

---

 

백준 - 단계별로 풀어보기 [1011] 

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

문제

 

처음 이동 할 때 -1, 0 , 1 을 이동할 수 있는 우주선은, 항상 k광년 이동시마다 k-1, k, k+1 광년만큼만 다시 이동할 수 있다.

x지점에서 y지점으로 이동하려고 할 때 필요한 최소한의 공간 이동 횟수를 구하는 프로그램을 작성하는 문제이다.

도착 직전의 이동거리는 반드시 1광년으로 해야한다.

풀이

 

 

최대 범위가 2의 31승이므로 범위가 매우 크기 때문에 반복문으로 해결하려고 할 경우 시간초과가 발생하는 문제이다.

또한, int형이 표현할 수 있는 최대 범위를 넘어서므로 long long 자료형으로 변수를 선언해주어야한다.

 

먼저 이 문제의 규칙을 알아보자.

마지막에는 반드시 1광년을 이동해야 하므로, k광년 이동시, k-1, k, k+1광년만 이동할 수 있다는 제약 조건에 의해, 마지막 이동 전에는 최대 2광년 이동이 가능하다. 또한, 최대 2광년이므로, 그 이전의 이동은 최대 3광년까지만 가능하다.

이러한 규칙에 의해서 최대거리를 이동하기 위해서는,
1광년이동 -> 2광년이동 -> 1광년이동(마지막이동)

1광년이동 -> 2광년이동 -> 3광년이동 -> 2광년이동 -> 1광년이동(마지막이동)

의 규칙을 따라야 한다.

 

1 + 2 + 1 = 4(최대이동거리) = 2 X 2(최대 속도 N = 2), 이동 횟수 = 3번

1 + 2 + 3 + 2 + 1 = 9(최대이동거리) = 3 X 3(최대 속도 N=3), 이동 횟수 = 5번

1 + 2 + 3 + 4 + 3 + 2 + 1 = 16(최대이동거리) = 4 X 4(최대 속도 N=4), 이동 횟수 = 7번

의 규칙을 가지게 된다.

 

따라서 최소의 차원이동을 하기 위해서는 우선 최대 이동거리만큼 이동을 하고, 모자란 거리 만큼을 중간에 넣어주면 된다.

예를 들어

 

11광년을 이동해야 한다면 먼저 1 - 2 - 3 - 2 - 1 로 9광년을 이동한다고 가정 한 후, 아래와 같이 규칙을 어기지 않는 선에서 남은 2광년에 해당하는 수를 끼워넣어주면 된다.

1 - 2 - 3 - 2 - 2 - 1 즉 총 6번의 이동을 통해 이동 할 수 있다.

 

하지만 만약, 최대이동거리인 9광년을 이동한 후, 남은 광년이 최대 속도인  N = 3을 넘기는 경우에는 어떻게 해결할 수 있을까? 마찬가지로 13광년을 이동해야 할 경우, 1 - 2 - 3 - 2 - 1 로 9광년을 이동한다고 가정 한 후, 4광년 만큼을 끼워 넣어주면 된다.

1 - 2 - 3 - 3 - 2 - 1 - 1 혹은, 1 - 2 - 3 - 2 - 2 - 2 - 1 식으로 바꿔 총 7번의 이동을 통해 이동할 수 있다.

 

즉 남은 거리가 최대 이동 속도를 넘지 않으면 차원이동 한번을 추가하면 되고, 남은 거리가 최대 이동속도를 넘을 경우에는 

여러 번의 차원 이동을 추가하면 된다는 것이다.

 

여기서 도출해낼 수 있는 규칙은, 모든 입력값은 임의의 자연수 N과 A에 대해서N^2 + A 꼴로 표현할 수 있으며 이 때의 최소 차원 이동 횟수는 N^2 만큼을 이동하기 위한  (2N-1) 번의 이동 횟수와 (A / N) 의 올림값을 더한 수라는 것이다.

 

예를 들어 위의 경우에는 입력값이 13광년이었을 때, (3 X 3) + 4의 형식으로 표현이 가능하고, 이에 위 공식을 대입하면 처음 9광년을 이동하기 위해 (2 x 3 - 1), 즉 5번의 이동 횟수가 필요하고, 나머지 거리 (4 / 3) = 1.333이므로 올림값을 2만큼의 이동 횟수가 필요하다는 것이다.

 

cmath혹은 math.h 파일 안에 있는 ceil 함수를 통해 올림값을 구해 2N-1과 더해주는 코드를 작성하면 시간초과 없이 풀이가 가능하다.

 

코드

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int main() {
    int num;
    scanf("%d",&num);
    for(int i = 0; i < num; i++)
    {
        long long x,y;
        long long move,max = 0;
        cin >>x>>y;
        while(max*max <= y-x)
            max++;
        max--;
        move = 2*max -1;
        long long rem = y-x - max*max;
        rem = (long long)ceil((double)rem / (double)max);
        move += rem;
        printf("%lld\n",move);
    }
}

 

평가

 

규칙을 도출해내는것이 간단하지 않은 문제이다. 마지막 이동 거리가 반드시 1이여야 한다는 것을 그냥 단순히 마지막은 1로 고정이라고 생각해서는 안되고, 1, 2, 3, 2, 1 꼴의 형태를 띄겠구나를 간파를 해야 규칙성을 알아낼 수 있는 문제이다.

 

단순 반복문으로는 무조건 시간초과가 발생하기 때문에, 해당 규칙을 알아내고 풀어야 한다.

또한 나머지 거리와 최대속도와의 관계를 분석하여 (A / N)의 올림값을 사용해야한다는 것을 도출을 해내야 문제 풀이가 가능하다. 대부분의 풀이가 코드만 덜렁 던져져 있어 이해를 끝까지 못하고 넘어가는 학생들이 많아, 글 주변은 없지만 최대한 상세히 풀이를 적어보았다. 

 

다소 까다로운 규칙성과 어려운 제약조건 떄문에 정답률이 27%인 고난도 문제이다.

못 풀었다고 하더라도 좌절하지 말고 설명을 차근차근 읽어보며 구현을 해보고 넘어가면 좋을 듯 하다.