BOJ 1011번 : Fly me to the Alpha Centauri

실버 1 문제라고 겁도 없이 건들였다가 어머어마하게 시간을 뺏겨 버렸다... 규칙을 찾기가 너무 어려웠고, 규칙을 찾은것 같아도, 식으로 풀어내는 과정이 너무 어려웠다.

 

기본적으로, 한 단계마다 속력의 변화가 ±1 이고, 출발과 도착시에 1의 속도를 맞춰야 하기에 무조건 속도를 증가시킬수는 없다. 따라서 속도를 증가시키다 감소 시켜야 한다.

 

처음에는 간단한 수식 한줄로 해결될줄 알았으나, 변수를 어떻게 설정하느냐의 문제였던 것 같다.

 

< Solution >

규칙을 찾기 위해 각 거리마다 최소 이동횟수를 적어보았다.

여기서 이동 횟수가 늘어나는 분기의 규칙성이 있는것같아 이동 횟수(n)에 연관된 변수 (An)을 설정하고, 각 횟수가 늘어나는 거리의 분기 (분기거리)에 따른 식을 만들었다.

그에 따라 일단 늘어나는 만큼 더해주는 식을 쭉 작성해 보았더니 아래와 같은 식을 도출할 수 있었다.

하지만, 식을 직관적으로 이해하는데 조금 복잡해 보여서 마음에 들지는 않는다...

아무튼, 위 식을 바탕으로 코드를 짜면, dp에 들어가는 것은 "거리"에 대한 값이 되고, 인덱스는 횟수 에 대한 값이 된다.

위 그림에 필기한 예제를 참고하면 쉽다.

 

<소스코드>

#include<iostream>
#include<vector>
using namespace std;
 
void Solve() {
    int t;
    long long x, y;
    cin >> t;
    for (int g = 0; g < t; g++) {
        cin >> x >> y;
        long long dist = y-x;
        vector <long long> v;
        int res = 0;
        v.push_back(0);
        v.push_back(1);
        for (int i = 2;; i++) {
            v.push_back(v[i - 1] + ((i) / 2));
            if (v[i - 1] <= dist && dist < v.back()) {
                res = i - 1;
                break;
            }
        }
        cout << res << endl;
        v.clear();
    }
}
 
int main() {
    Solve();
}

<문제>

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

1011번: Fly me to the Alpha Centauri