[Baekjoon] 17451번 : 평행 우주

1. 문제

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

• 그리디 문제

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

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

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

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

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

// 입력
첫째 줄에 n(1 ≤ n ≤ 3·105)이 주어진다.

둘째 줄에 n개의 정수 v1, v2, …, vn이 공백을 사이에 두고 주어진다. 
모든 정수 1 ≤ i ≤ n에 대해 1 ≤ vi ≤ 109을 만족한다.

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

// 예제 입력 1 
5
300 400 500 400 300

// 예제 출력 1 
900

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

2. 핵심 아이디어

3. Python 문제풀이

import sys
input = sys.stdin.readline

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

for i in range(n-1, -1, -1) :
  if result <= v[i] :
    result = v[i]
  else :
    if result % v[i] :
      result = (result // v[i] + 1) * v[i]
      
print(result)

4. Java 문제풀이