[c++] 백준 #1011 Fly me to the Alpha Centauri

난이도 순서대로 풀기 리스트에 있어서 풀게 된 문제이다. 어렵지 않았지만, 실버1보다는 조금 더 난이도가 있었겠다 싶은 그런 문제이다. 내가 좋아하는 스타일의 깔끔한 그리디 문제이다. 

www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

<풀이>

문제 설명을 짧게 해보자면, x 지점에서 y 지점까지 갈 때 공간이동 장치의 작동횟수를 계산하는 것이다. 공간 이동장치는 맨 처음에는 거리 1만큼을 움직일 수 있고, 작동시킬 때마다 이전에 움직였던 거리-1, 거리, 거리+1 중에서 움직일 수 있고, 도착하기 직전에는 반드시 거리 1로 속력을 줄여야 한다. 숫자 범위가 2^31로 전체 int 범위를 다 아우르기 때문에, 시간초과나 메모리 초과가 나지 않게 풀어야 푸는 것이 중요하다.

 

반드시 도착하기 직전에 속력을 1로 줄여야 한다는 조건 때문에 최대 속력을 N이라고 하면, 적어도 1+ 2 + 3 + ... + N + N-1 + N-2 + ... + 3 + 2 + 1 이런 식으로 한번 최고점까지 찍은 후, 다시 감소시키는 형태의 시퀀스가 최소한의 작동횟수를 만들어낼 것이다.(N = (N-1) + 1으로 쪼갤 수 있기 때문에, 최고 속력에서 1씩 낮출 때마다 항상 작동횟수가 최소 1만큼 더 늘어날 것이다.)

 

상황을 간단하게 하기 위해서, 공간이동 장치가 N으로 이동하는 횟수를 2번으로 두고, (속력 N을 2번 더 유지) 1 + 2 + 3 + ... + N + N + N-1 + N-2 + ... + 3 + 2 + 1의 시퀀스의 합을 계산해보면 N(N+1)/2 * 2 = N(N+1)이 된다. 따라서, int 범위(20억)의 거리를 표현하기 위해서 필요한 부분합 배열의 길이는 대략 20만으로 잡으면 된다.

 

주어진 거리 안에서 돌아갈 수 있는 최고속력을 idx로 두어서 계산하였다. 

이제 주어진 거리에서 증가 감소 시퀀스(1~N~1)로 이동하는 거리 외에 나머지 거리는 속력을 유지하면서 이동하는 거리가 될 것인데, 높은 속력을 최대한 많이 유지하는 것이 좋으므로, 이를 그리디하게 계산해주면 된다. 이 부분에서의 시간 복잡도를 계산하기는 애매하지만, 남은 거리는 많아봤자 40만 정도일 것이기 때문에 오래 걸리지 않으므로 주어진 시간 내에 풀 수 있다.

 

#include <iostream>
#include <string>
using namespace std;

long long psum[200010];

int main(){
    for (int i=1; i<200010;i++){
        psum[i] = psum[i-1] + i;
    }
    int T; cin >> T;
    while(T--) {
        int x, y; cin >> x >> y;
        int diff = y - x; // always >=0
        int idx = 1;
        int ans = 0;
        for(; idx<200010;idx++){
            if (2 * psum[idx] > diff) break;
        }
        ans += 2 * (idx-1);
        int residue = diff - 2 * psum[idx-1];
        // we will add as many as possible high number
        for(int t=idx; t>=1; t--){
            while(residue >= t){
                residue -= t;
                ans ++;
            }
        }
        cout << ans << '\n';
    }

    return 0;   
}

< 느낀 점>

풀고나서 다른 사람들도 비슷하게 풀었나 싶어서 알아봤는데, 제곱수가 될때마다(1, 4, 9, 16, ...) 작동 횟수가 하나씩 늘어나는 규칙이 있다고 한다. 그렇게 하면 3가지 조건(그 사이 숫자들 케이스 고려)만 따져서 정답을 빠르게 알 수 있다. 그래서 수학문제 였구나 싶다. 물론 내 풀이도 결국 N^2을 고려한 풀이인 것 같긴 한데, 좀 더 간단하게 짜는 방법이 있었다는 것을 알게 되었다. 뭐 어떻게 풀든지는 자유지만, 수학 문제 같은 이런 문제는 숫자 노가다를 통해 규칙을 발견하는 게 중요한 것 같은데 다음부터는 이런 풀이도 떠올릴 수 있으면 좋을 것 같다.