[ 백준 ] 1011 Fly me to the Alpha Centauri

📌 Problem

x부터 y까지 (0 <= x < y <= Integer.MAX_VALUE) 공간이동을 한다. 공간이동은 이전 공간 이동 거리에 따라 선택할 수 있다. 이전 공간 이동한 거리가 K이면 K - 1, K, K + 1 중에 하나를 선택하여 다음 공간을 할 수 있다. 예를 들어 100에서 110으로 공간 이동을 했다면 10을 이동한 것이기 때문에 110에서는 9, 10, 11을 이동하여 119, 120, 121으로 공간 이동이 가능하다. 출발 위치와 도착 위치가 주어졌을 때 최소한의 공간 이동 횟수를 구하면 된다.

📌 Solution

사실 주어진 출발 위치와 도착 위치를 각각 고려할 필요는 없다. 공간 이동은 거리 단위이기 때문에 총 얼마를 이동하면 되는지만 알면 된다. 출발 위치가 N이고 도착 위치가 N + K 일 때 필요한 것은 K 뿐이다.

int start = ...;
int end = ...;
int distance = end - start;

시간 제한만 없다면 BFS으로 해결이 가능하다. 하지만 실제로 구현을 해본 결과 거리가 100 정도만 되어도 시간이 오래 걸린다. 하지만 이를 구현해서 결과를 보는 것으로 어떠한 규칙이 있는지를 확인할 수 있다. 그렇기 때문에 아래의 코드를 실행해보고 규칙이 보이면 스스로 solution을 구현해 보는 것을 추천한다.

📌 Code

public void solve() throws IOException {
    StringTokenizer tokenizer;
    int T = Integer.parseInt(reader.readLine());
    while (T-- > 0) {
        tokenizer = new StringTokenizer(reader.readLine());
        int distance = -Integer.parseInt(tokenizer.nextToken())
                + Integer.parseInt(tokenizer.nextToken());
        result.append(warp(distance)).append("\n");
    }
}

private int warp(int distance) {
    int warp = 1;
    while (true) {
        distance -= (warp + 1) / 2;
        if (distance <= 0) return warp;
        warp++;
    }
}