문제 링크: https://www.acmicpc.net/problem/1011

Thumbnail: Photo by NASA Hubble Space Telescope (Unsplash)

골드 5 치고는 생각보다 풀이가 쉬웠습니다. 방법만 떠올리면 어렵지 않게 풀 수 있는 것 같습니다.

풀이

유익했던 한마디

처음 문제를 봤을 때는 이전에 풀었던 숨바꼭질을 생각해 BFS 풀이를 떠올렸다가, \(x\)와 \(y\)의 범위가 \(2^31\)까지인걸 확인하고 빠르게 포기했습니다 ㅎㅎ..

풀이가 잘 감이 오지 않았는데, 질문 게시판에 있던 한 답변의 글을 보고 아이디어를 쉽게 떠올렸습니다.

입력으로 주어진 거리가 \(x\)일 때 최소 장치 작동 횟수 \(y\)를 구하는 게 아니라, 장치 작동 횟수 \(x\)가 주어질 때 최대 갈 수 있는 거리 \(y\)를 구한다고 보면 쉬워집니다.

핵심 개념

우주선은 이전에 이동한 거리 \(d\)에 대해, 이번에는 \(d-1\), \(d\), \(d+1\)중 한가지 거리로만 이동할 수 있습니다.

다시 말하면, 1회 이동 거리를 늘리는 데도, 줄이는 데도 1씩 사용되므로 이동 거리 변화는 피라미드 꼴로 나타남을 이해할 수 있습니다.

그럼 이제, \(x\)와 \(y\)사이를 최소 이동 횟수로 이동하려면 어떤 방식으로 이동해야 할지 생각해야 합니다.

간단하게 생각해서, 이동 거리를 최대한 늘려서 위에서 설명한 피라미드꼴만큼 이동하고, 남는 거리는 피라미드 안의 이동 거리 중에서 적절히 골라 추가로 더 이동하는 방식을 생각했습니다.

피라미드 이동 거리 계산

피라미드 꼴의 이동 거리가 어떻게 이루어지는지 먼저 규칙을 파악해봅시다.
피라미드를 구분하기 위한 인덱스 번호 \(i\)는 해당 피라미드에서 가장 크게 이동한 거리입니다.

• i = 0
  • 아예 이동하지 않았습니다.
  • 총 이동 거리 = 0
  • 총 이동 횟수 = 0
• i = 1
  • 1
• 총 이동 거리 = 1
• 총 이동 횟수 = 1
• i = 2
  • 1 2 1
  • 총 이동 거리 = 4
  • 총 이동 횟수 = 3
• i = 3
  • 1 2 3 2 1
  • 총 이동 거리 = 9
  • 총 이동 횟수 = 5
• ...

\(i = 3\)일 때와 \(i = 2\)일 때를 비교해, 이동 거리가 어떻게 변화하는지 비교해봅시다.

• i = 2 / 1 2 1
• i = 3 / 1 2 3 2 1
  • 1 2 1 / 2 / 3 으로 쪼개서 생각
  • [i=2] (이전항) / i-1 / i 꼴로 정리됩니다.

\(i\)에 따른 이동 거리를 저장할 배열을 pyramids라고 할 때, pyramids[i]는 다음과 같이 계산할 수 있습니다.

pyramids[i] = pyramids[i-1] + i-1 + i = pyramids[i-1] + 2*i - 1

이동 횟수의 경우, \(2 \times i - 1\) 꼴로 계산해낼 수 있으니 별도로 저장하지 않아도 됩니다.

피라미드 꼴의 이동 거리는 반복문으로 계산하면 됩니다. 아래는 현재 pyramids 에 \(i\)까지의 데이터가 없을 경우, 그 값을 계산해 저장하는 코드입니다.

for j in range(len(pyramids), i + 1):
    pyramids.append(pyramids[j - 1] + 2 * j - 1)

목표 거리까지의 이동 횟수 계산하기

이제, pyramids[i]꼴로 피라미드꼴로 이동한 총 거리를 구할 수 있습니다.

하지만, 언제나 pyramids[i]가 이동해야 하는 거리인 \(y - x\)와 같지는 않습니다.
따라서, pyramids[i]에서 적절히 몇 번 더 이동해 거리를 맞춰야 합니다.

현재 이동한 거리를 base_dist라 하고, 이는 pyramids[i]로 초기화됩니다.
1회 더 이동할 거리를 dist라고 할 때, dist를 현재 사용하는 피라미드의 \(i\)값부터 1까지 감소시켜가며 아래를 반복합니다:

• base_dist + dist가 y - x보다 같거나 작을 동안:
  • dist만큼을 이동 거리에 더하고, 이동 횟수를 1 증가시킵니다.
• 이후 dist를 1씩 감소시켜 가며 위의 과정을 반복합니다.

전체 코드

input = open(0).readline
pyramids = [0, 1]
for _ in range(int(input().strip())):
    X, Y = map(int, input().split())
    goal_dist = Y - X

    i = 1
    cnt = 0
    while pyramids[i] < goal_dist:
        i += 1
        if len(pyramids) <= i:
            for j in range(len(pyramids), i + 1):
                pyramids.append(pyramids[j - 1] + 2 * j - 1)
    # while문 종료 이후의 i는 목표 거리를 넘거나 같은 최소의 i값이다.
    if pyramids[i] == goal_dist:
        print(2 * i - 1)
        continue
    # i-1의 이동 거리에 추가 이동 횟수를 더해 조절하면 된다.
    base_dist = pyramids[i - 1]
    cnt = 2 * i - 3      # 2 * (i-1) - 1 = 2 *  - 3
    dist = i - 1
    while base_dist < goal_dist and dist > 0:
        while base_dist + dist <= goal_dist:
            base_dist += dist
            cnt += 1
        dist -= 1
    print(cnt)