[Python/파이썬] 백준 17451번 평행 우주

https://www.acmicpc.net/problem/17451

 

코드

import sys
input = sys.stdin.readline

n = int(input())
v = list(map(int, input().split()))

ans = v[-1]
for i in range(n-2, -1, -1):
    if ans % v[i] != 0:
        ans = (ans//v[i]+1)*v[i]
print(ans)

 

처음에 Parametric Search로 풀이했다가 시간 초과가 발생하였는데, Parametric Search 알고리즘만 하면 시간 복잡도가 O(logN)인데 조건 검사할 때마다 O(N)이 추가로 필요해서 그런 것 같다. 그래서 다시 살펴보니 Greedy로 풀이할 수 있을 것 같아서 바꾸었다.

 

행성은 1에서 N까지 순서대로 탐사하는 것이므로 처음 출발할 때 필요한 가장 최소의 속도를 구하려면 거꾸로 살펴보면 될 것 같았다. 문제의 조건은 ①속도는 현재 속도에서 내릴 수만 있고, ②행성 간 필요한 속도의 양의 정수 배수로 이동 가능하다고 했다. 그랬기에 우선 ans를 가장 마지막 속도로 해놓고, 왼쪽으로 하나씩 오며 v[i]의 양의 정수 배수가 되지 않는 경우에는 ans보다 크면서 v[i]의 양의 정수 배수인 수 중 가장 작은 수를 ans로 재할당해주면 된다. 이렇게 가장 첫번째 원소까지 이 과정을 반복한다면 처음 출발할 때 필요한 가장 최소의 속도를 구할 수 있다.