Hanbit the Developer
[Python] 백준 1011번: Fly me to the Alpha Centauri 본문
1011번: Fly me to the Alpha Centauri
우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행
www.acmicpc.net
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를 거꾸로 돌아준다.
그 이유는, 뒤로갈수록 담고 있는 범위가 더 넓기 때문이다.
'Algorithm > 백준' 카테고리의 다른 글
[Python] 백준 1181번: 단어 정렬 (0) | 2021.05.07 |
---|---|
[Python] 백준 1874번: 스택 수열 (0) | 2021.05.06 |
[Python] 백준 2206번: 벽 부수고 이동하기 (0) | 2021.05.03 |
[Python] 백준 1654번: 랜선 자르기 (0) | 2021.04.30 |
[Python] 백준 11053번: 가장 긴 증가하는 부분 수열 (0) | 2021.04.27 |