[백준] 1011 - Fly me to the Alpha Centauri (C++)

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

공간이동 장치를 이용하는 우주선이 있다. 공간이동 장치 작동 시의 에너지 소모를 줄이기 위해 x 지점에서 y 지점을 향해 최소한의 작동 횟수로 이동하려고 한다. 이 공간이동 장치는 특별한 규칙대로 작동한다.

1. 이전 작동시기에 k광년을 이동했을 때는 k-1, k 혹은 k+1 광년만을 다시 이동할 수 있다.
2. y 지점에 도착해서도 공간이동 장치의 안정성을 위하여 y 지점에 도착하기 바로 직전의 이동 거리는 반드시 1 광년으로 하려 한다.

 

최종적으로 x 지점부터 정확히 y 지점으로 이동하는데 필요한 공간이동 장치 작동 횟수의 최솟값을 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 0 ≤ x < y < 2^31

 

y 지점에서 x 지점을 뺀 거리와 이동한 거리를 직접 써보면 규칙을 찾을 수 있다.

• 1 → 1
• 2 → 1 1
• 3 → 1 1 1
• 4 → 1 2 1
• 5 → 1 2 1 1
• 6 → 1 2 2 1
• 7 → 1 2 2 1 1
• 8 → 1 2 2 2 1
• 9 → 1 2 3 2 1
• 10 → 1 2 3 2 1 1

 

이때 양쪽에서 1, 2, 3, ... 순서로 대칭으로 늘어나고, y 지점에서 x 지점을 뺀 거리의 제곱근 값이 이동한 거리에 나타날 수 있는 수의 최댓값이라는 걸 알 수 있다. 거리의 제곱근 값을 이용해 작동 횟수를 갱신하면서 진행하면 된다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. 테스트 케이스 개수 T 입력받기
   1. x, y 입력받고 거리 구하기
   2. 거리의 제곱근 값(= 이동 거리 최댓값) 구하기
      1. 그 값보다 1 작은 값까지 반복문을 진행하며 2를 곱해 거리에서 빼고 작동 횟수에 2씩 더하기
      2. 제곱근 값부터 1까지, 남은 거리에서 빼면서 작동 횟수 갱신하기
   3. 작동 횟수 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해 보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

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

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

    int t;
    cin >> t;
    while (t--) {
        long long int x,y,d,ans=0;
        cin >> x >> y;
        d = y-x;
        
        int mx = sqrt(d);
        for (int i=1; i<mx; i++) {
            d -= i*2;
            ans +=2;
        }
        for (int i=mx; i>0; i--) {
            ans += d/i;
            d -= d/i * i;
        }

        cout << ans << '\n';
    }
}