[백준 알고리즘/BOJ/C++] 1011 Fly me to the Alpha Centauri

 

 

공간이동 장치 작동 횟수의 최솟값을 구하는 문제다

 

1) x에서 y까지 가야 하는데 우주선의 공간이동 장치는 k-1, k, k+1 만큼씩 움직일 수 있다

2) 제일 처음엔 1광년 움직일 수 있고, y에 도착하기 직전에도 1광년을 움직일 수 있다

 

양쪽에서 같이 계산해줘야 한다

x에서 한칸, y에서 한칸

x에서 두칸, y에서 두칸

·

·

 

 

#include <iostream>
using namespace std;
 
int t, x, y;
 
void get(int cnt, int i) {
    if (x >= y)
        cout << cnt << "\n";
    else if (x + i >= y) // x가 최대 거리로 갔을 때 현재 y좌표 이상이면 횟수 +1이 정답
        cout << cnt + 1 << "\n";
    else { // x, y 둘 다 최대 거리로 이동하고 다음으로 넘어가기
        x += i;
        y -= i;
        get(cnt + 2, i + 1);
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    while (t--) {
        cin >> x >> y;
        get(0, 1);
    }
}

 

x엔 i씩 더해주고, y엔 i씩 빼준다

그리고 2씩 count 해준다

x가 y와 같거나 x가 y를 넘어버리면 바로 count를 출력한다

else if로 x가 한번만 더 움직이면 y좌표를 넘는지도 체크해준다