<2022모각코/TIL> [백준/python] 17451 - 평행우주

17451번: 평행 우주

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
speed = list(map(int, input().split()))
earth = speed[-1]

while len(speed) != 1:
    speed.pop()
    if earth > speed[-1]:
        if earth % speed[-1] != 0:
            earth = speed[-1] * ((earth // speed[-1]) + 1)
    else:
        earth = speed[-1]

print(earth)

알고리즘:

뒤에서 부터 순회하여, 현재 지구 스피드가 speed 요소보다 작으면, 해당 스피드 요소로 지구의 스피드를 업데이트 해주고,

만약 크다면 해당 스피드 요소에 (지구스피드//해당 스피드) + 1 값으로 지구 스피드를 업데이트 해준다.

 

이진 탐색일 줄 알아서 풀었는데 그냥 그리디..? 인 듯 하다. 처음에 앞에서부터 탐색하다가

5
300 400 500 300 400

이 반례에 막혀서 뒤로 했더니 됐다.