[C++] 백준 1011: Fly me to the Alpha Centauri

문제 이해

- 지구에서 특정 행성으로 공간 이동을 한다고 하자.

- 이전에 k광년 이동 시, k-1 or k or k+1 광년만큼만 이동할 수 있다.

- x에서 y까지 가는데  필요한 최소한의 공간 이동 장치 작동 횟수를 구하라.

- 단, y 지점 도착하기 바로 직전에는 반드시 1광년만큼만 이동해야 한다.

 

<조건>

- 시간 제한: 2초

- 메모리 제한: 512MB

 

<입력>

T: 테스트 케이스

x: 현재 위치 (0 ~ 2^31-1)

y: 목표 위치 (0 ~ 2^31-1)

 

<출력>

- 각 테스트 케이스에 대하여 x에서 y까지 정확히 도달하는데 필요한 최소한의 공간이동 횟수를 구하라.

 

 

---

문제 풀이

뭔가 수열 문제 같기도 했고, 투포인터처럼 풀어볼까도 생각했던 문제이다.

 

결국 30분 시간제한을 넘겨 인터넷 풀이를 참고하였다.

 

총 2가지의 풀이를 참고하였는데

첫 번째는 제곱근의 값을 이용하는 방법

두 번째는 투포인터 느낌으로 푸는 방법이다.

 

 

---

첫 번째 풀이 - 제곱근

첫 번째 풀이부터 살펴보자.

먼저 시작과 끝은 각각 이동 거리가 1이다.

그 사이에 이동 거리는 분명 변동이 있겠지만 커졌다가 작아지는 느낌일 것이다.

 

 

핵심은 바로 최대 이동거리이다.

거리가 4일 때,

1 2 1로 이동할 것이고,

최대 이동거리는 2, 이동 횟수는 3이다.

 

 

거리가 9일 때,

1 2 3 2 1으로 이동할 것이고,

최대 이동거리는 3, 이동 횟수는 5이다.

 

 

거리가 16일 때,

1 2 3 4 3 2 1으로 이동할 것이고,

최대 이동거리는 4, 이동 횟수는 7이다.

 

 

즉, 거리가 제곱수일때,

최대 이동거리는 거리의 제곱근이 되고,

이동 횟수는 '거리의 제곱근 * 2 - 1'이다.

 

 

그런데 거리는 제곱수만 있지 않을 것이다.

4 ~ 9 사이에는 분명 5 ~ 8이 있다.

이들의 경우 어떻게 될까?

 

바로 제곱근과 그 제곱근을 반올림한 값을 이용하면 구할 수 있다.

 

 

아래 참고 포스팅의 자료를 보면

위와 같이 진행된다.

 

즉 제곱근의 값 <= 반올림한 값일땐 2 * 반올림값 - 1

제곱근의 값 > 반올림한 값일땐 2 * 반올림값

 

으로 구할 수 있다!

---

전체 코드(1)

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

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

    int t;
    cin>>t;
    while(t--){
        int x, y, result;
        cin>>x>>y;

        int distance = y-x;
        double dpow = sqrt(distance);
        int pow = round(dpow);

        if(dpow <= pow) cout<< pow * 2 -1 <<"\n";
        else cout<<pow*2<<"\n";
    }
    
    return 0;
}

 

 

 

---

두 번째 풀이 - 투포인터의 원리 이용

처음과 끝의 이동 거리는 분명 1일것이다.

물론 거리가 1일경우 둘 중 하나는 이동하지 않겠지만 일단은 1이다.

 

 

위의 풀이처럼

이동 거리가 커졌다가 작아지는 걸 이용하는데

처음과 끝에서 동시에 출발하여 이동거리를 1씩 늘려가며 중앙을 향해 간다고 하자.

 

1 1

1 2 2 1

1 2 3 3 2 1

위와 같이 진행될 것이다.

 

 

 

그러나, 거리가 위 숫자들의 합만 존재하는 것이 아닐 것이다.

 

 

 

예를 들어 거리가 10이라면

1 2 2 1만큼 간 뒤에

1 2 3 3 2 1만큼 가면 초과하여 간 것이므로 불가능하다.

 

 

이럴 땐

한 쪽만 3을 가고, 나머지는 남은 거리만큼만 이동하자.

1 2 3 1 2 1 처럼 될 것이다.

 

 

이럴수가 이건 문제에서 말한 규칙과 안 맞지 않는가?

하지만 이건 순서를 바꿀경우 해결할 수 있다.

 

1 2 3 2 1 1과 같이 순서를 바꿀경우 해결될 것이다.

 

 

 

이걸 코드로 구현해주면 된다.

 

 

---

전체 코드(2)

#include <iostream>
using namespace std;

int solve(int dist){
    int ans = 0;
    int vmax = 1;
    while(dist > 0){
        if(dist >= vmax * 2){
            dist -= vmax * 2;
            ans += 2;
        }else if(dist >= vmax){
            dist -= vmax;
            ans += 1;
        }else{
            dist -= dist;
            ans += 1;
        }
        vmax++;
    }

    return ans;
}

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

    int t;
    cin>>t;
    while(t--){
        int x, y;
        cin>>x>>y;
        cout<<solve(y-x)<<"\n";
    }
    
    return 0;
}

 

 

 

---

참고 포스팅

이게 첫 번째 풀이 참고 링크이고,

https://jaynamm.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-1011%EB%B2%88-Fly-me-to-the-Alpha-Centauri

[백준 알고리즘] 1011번 : Fly me to the Alpha Centauri

 

 

이게 두 번째 풀이 참고 링크이다.

https://wonsang98.tistory.com/entry/%EB%B0%B1%EC%A4%80-1011%EB%B2%88-Fly-me-to-the-Alpha-Centauri-C

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