[백준 1011번] Fly me to the Alpha Centauri

문제 링크: 1011번 Fly me to the Alpha Centauri

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

 

n회 이동으로 최대 거리를 이동할 때 각 경로를 표시하면 다음과 같다.

 

n=1일 때, [1]

n=2일 때, [1 1]

n=3일 때, [1 2 1]

n=4일 때, [1 2 2 1]

n=5일 때, [1 2 3 2 1]

...

 

그러면 다음과 같이 수열의 일반항을 구할 수 있다.

 

홀수일 때는 1, 4, 9, 16, ... → a_n = n^2

짝수일 때는 2, 6, 12, 20, ... → a_n = n^2 + n

→

여기서 쓸데없는 고민을 너무 많이 했다.

짝수일 때까지는 고려할 필요가 없었다!

사용할 수는 있지만, 복잡해진다.

 

표를 그리거나 순서도를 그려볼 때,

어떤 변수를 설정할지, 어느 항목의 변화를 추적하고 있는 것인지

얼버무리지 말고 명확하게 기록하자.

 

#include <iostream>
using namespace std;

long long test(long long distance) {
    long long n, dmax;
    for (n = 1; ; n++) {
        dmax = n * n; // n일 때 최대이동거리
        if (dmax > distance) {
            break;
        }
    }
    
    /*
    비슷한 문제를 풀 때마다
    '이전으로 돌아가서 한 번 더 계산해도 되나?'와 같은 생각을 했었는데,
    답은, 된다. 고민하지 말자 이제는...!
    */
    
    if ((n-1) * (n-1) == distance)
        return 2 * n - 3; // 이동횟수 = 2n-1인데, n = n-1 상태이므로, 이동횟수 = 2(n-1)-1
    else if (distance <= n*n - n)
        return 2 * n - 2;
    else
        return 2 * n - 1;
}

int main(void) {
    int cases;
    cin >> cases;
    
    for (int i = 0; i < cases; i++) {
        long long x, y, distance;
        cin >> x >> y;
        distance = y - x;
        cout << test(distance) << '\n';
    }
    
    return 0;
}