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

www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

import sys
input = sys.stdin.readline


def setJumpCounts(maxIndex):
    global jumpCounts
    lastIndex = 1
    i = 2

    while lastIndex < maxIndex:
        rep = (i+1)//2
        jumpCounts.append(jumpCounts[i-1]+rep)

        lastIndex = jumpCounts[-1]
        i += 1


# [0,1,2,4,6]에서 4의 의미: 거리의 차이가 4인 곳까지의 점프 횟수가 해당 index인 3이다.
# 1 2 3 4 5 6 (인덱스)
# 1 2 3 3 4 4 (값)
jumpCounts = [0, 1]

T = int(input())
diffs = []

for _ in range(T):
    x, y = map(int, input().split())
    diffs.append(y-x)

setJumpCounts(max(diffs))
for i in range(T):
    for j in range(len(jumpCounts)-1, 0, -1):
        if jumpCounts[j-1] < diffs[i] <= jumpCounts[j]:
            print(j)
            break

해당 코드에서 jumpCounts[i]의 의미는, 거리의 차이가 jumpCounts[i]인 곳까지의 점프 횟수가 i라는 것이다.

이러한 jumpCounts를 구하는 함수가 setJumpCounts()인데, 함수의 파라메터에 max(diffs)를 넣어서 필요한 정보만 얻게끔 설계하였다.

 

다음은 max(diffs)가 100일 때의 jumpCounts이다.

[0, 1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 36, 42, 49, 56, 64, 72, 81, 90, 100]

 

이렇게 jumpCounts를 구했으면, 출력을 해줘야하는데, 각 테스트케이스에 대해 jumpCounts를 거꾸로 돌아준다.

그 이유는, 뒤로갈수록 담고 있는 범위가 더 넓기 때문이다.