[백준] 17451번 평행 우주 [Python] - 그리디

 

이동할 행성마다 빠져나가기 위해 요구하는 최소 속도가 있다.

출발하면 속도를 유지하거나 늦추기만 가능하며, 최소 속도의 정수배일 때만 그 행성을 지나갈 수 있다.
모든 행성을 지나가기 위한 최소 출발 속도를 구하는 문제

문제

서기 2XXX년, 지구가 소행성과 충돌할 위기에 처했다! 똑똑한 과학자 키파는 평행 우주를 누비며 지구를 대신할 행성을 찾는 막중한 임무를 맡게 되었다.

우리는 현재 지구$($=행성 0$)$에 있다. 여러 요인을 고려한 결과, 행성 1, 행성 2, …, 행성 $($n-1$)$을 순서대로 확인하고 지구$($=행성 n$)$에 돌아오는 것이 비용상 최적임을 알아냈다. 모든 정수 1 ≤ i < n에 대해, 행성 i은 지구가 아니다.

지구에는 "초고속 걷기 기계"라는, 속도를 원하는 만큼 올릴 수 있는 특수한 장치가 있다. 지구를 벗어나면 속도를 떨어뜨릴 수 있을 뿐 높일 수는 없다.

다음 지역에 가기 위해서는 원칙적으로는 필요한 속도를 정확히 맞춰야 하지만, 다행히도 평행 우주는 일정한 간격을 두고 있기 때문에 필요한 속도의 양의 정수 배로도 다음 지역으로 이동할 수 있다. 또한, 충분히 빠른 속도로 이동 중이며, 지구의 대체 행성으로 적합한지 아닌지는 도착한 뒤 바로 알 수 있기 때문에 어떤 행성에서는 도달한 뒤 속도를 유지한 채 다음 행성으로 이동할 수도 있다.

모든 1 ≤ i ≤ n에 대해, 행성 $($i-1$)$에서 행성 i로 이동하는 데 필요한 $($최소$)$ 속도 $v_i$가 주어진다. 지구에서 올려야 하는 속도를 최소화하시오.

입력

첫째 줄에 n$($1 ≤ n ≤ 3·${10}^5$$)$이 주어진다.

둘째 줄에 n개의 정수 $v_1,v_2,\dots ,v_n$이 공백을 사이에 두고 주어진다. 모든 정수 1 ≤ i ≤ n에 대해 1 ≤ $v_i$ ≤ ${10}^9$을 만족한다.

출력

수 하나를 출력한다. 이 수는 지구에서 올려야 하는 속도의 최솟값이다.

17451번: 평행 우주 $acmicpc.net$

 

import sys
from math import lcm
N = int(sys.stdin.readline())
li = list(map(int, sys.stdin.readline().split()))
c_v = 0
# 마지막 행성 속도부터 시작해서 그 전 행성의 탈출 속도와 비교
for p_v in li[::-1]:
    # 이전 행성이 요구하는 속도가 더 빠를 때는 그 속도를 저장
    if c_v < p_v:
        c_v = p_v
    # 이전 행성이 요구하는 속도가 더 느리면서 
    # 약수가 아닐 때, 그 속도의 배수 중에 가장 가까운 큰 수를 속도로 저장
    elif c_v % p_v:
        c_v = p_v*(c_v//p_v+1)

print(c_v)

 

 

 

예제 입력 1 

5
300 400 500 400 300

예제 출력 1 

900

노트

행성 1에 가기 위해 필요한 것보다 세 배의 속도로, 행성 2의 경우 두 배의 속도로 이동하면, 지구에서는 900의 속도만 쌓으면 된다.