[랜덤] BOJ 1011 - Fly me to the Alpha Centauri (C++)

문제 링크

백준 1011

풀이 시간

아이디어: 20분
코딩: 10분

문제 풀이

조건)

1. 처음과 끝 직전에는 무조건 속도 1로 도달해야한다.
2. K번째 턴의 속도 V[K]는 V[K-1]-1, V[K-1], V[K-1]+1

조건을 해결하기 전 먼저 어떤 규칙이 있을 것 같다고 생각했다.

예를 들어 A=0, B=10이라고 가정하자.
구간의 길이는 총 B-A = 10이다.

눈으로 계산해보면

0 -(+1)-> 1, 1 -(+2)-> 3, 3 -(+3)-> 6, 6 -(+2)-> 8, 8 -(+1)-> 9, 9 -(+1)-> 10 이다.
가운데 값을 기준으로 양쪽으로 내려가는 것을 볼 수 있다.
무엇보다 끝에 +1이 두번 나오는 것을 통해, 남는 거리만큼 +1을 하면 될 것 같다고 생각했다.

이를 표로 남겨보자
왼쪽 칼럼을 속도라고 했을 때

개수, 남은 개수

---

1| 2 , 8
2| 2 , 4
3| 1 , 1

잘 보면 속도3일 때, 남는 거리 1이 있는 것을 알 수 있다.

이를 통해 프로그래밍 해보자.

코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>

#define ll long long

using namespace std;

ll t, a, b;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> t;
    while(t--) {
        cin >> a >> b;
        ll gap = b-a;
        ll remain = gap;
        ll res = 0;
        bool flag = false;
        for(int i=1;i<gap;i++) {
            flag =false;
            for(int j=1;j<=2;j++) {

                if(remain - i >= 0) {
                    remain -= i;
                    res++;
                }
                else {
                    flag = true;
                    break;
                }
            }
            if(flag)
                break;
        }
        if(remain > 0) {
            res++;
        }
        cout << res << "\n";
    }
    return 0;
}

x와 y가 2^31 이므로 타입을 조심하자.