[BOJ/Python] 백준 17451번 - 평행 우주

백준 #17451 평행 우주

17451번: 평행 우주

import sys
import math
input = sys.stdin.readline

n = int(input())   # 행성 수
planet = list(map(int, input().split()))   # 각 행성으로 이동하는 데 필요한 (최소) 속도
speed = planet[-1]

for i in range(n-2, -1, -1):
  if planet[i] < speed:
    if speed % planet[i] == 0:
      continue
    speed = ((speed // planet[i]) + 1) * planet[i]
  else:
    speed = planet[i]

print(speed)

각 행성의 스피드가 담겨있는 리스트를 거꾸로 순회한다. 뒤에 있는 행성의 속도가 앞에 있는 행성의 속도보다 작을 경우 해당 속도로 그대로 갈 수 있고, 뒤에 있는 행성의 속도가 앞에 있는 행성의 속도보다 클 경우 앞에 있는 행성의 속도 배수로 가야 한다. 마지막 행성의 스피드를 먼저 담아놓고, 거꾸로 차례대로 행성의 스피드를 본다.

 

결국 역순으로

1. 현재 속도가 행성 i의 속도보다 작음 → 현재 속도를 행성 i 속도로 갱신
2. 현재 속도가 행성 i의 속도보다 큼 → 행성 i의 속도가 현재 속도로 나누어 떨어짐 → 현재 속도로 계속 진행
3. 현재 속도가 행성 i의 속도보다 큼 → 행성 i의 속도가 현재 속도로 나누어 떨어지지 않음 → 현재 속도를 현재 속도보다 처음으로 큰 행성 i의 속도 배수로 갱신

계속 100% 떴는데 틀렸다고 해서 열받았네 ,,