문제 바로가기
문제:
서기 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을 만족한다.
출력:
수 하나를 출력한다. 이 수는 지구에서 올려야 하는 속도의 최솟값이다.
풀이:
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
N =int(sys.stdin.readline())
board = list(map(int,sys.stdin.readline().split(" ")))
res = 0
for i in range(N-1, -1, -1):
if res <= board[i]:
res = board[i]
else:
if res % board[i]:
res = (res // board[i] + 1) * board[i]
print(res)
거꾸로 돌면서 확인한다.
끝까지 가야 가능한거니깐
필요한 값보다 지금 행성 값이 더 크면서 안 나눠떨어지면 몫만큼 더해준다.
만약 res 500 이고 행성값이 400이면 800이 되어햐 하니깐, 500 // 행성값 + 1 * 행성값 을 해주면된다.
댓글