풀이 전략은 다음과 같습니다.
문제가 살짝 헷갈리는데요, 예시를 따라가보며 정리해보겠습니다.
예시에서 행성을 통과하는 데 필요한 속도가 각각 300 400 500 400 300이라고 되어있습니다.
- 필요한 속도가 300 400 500 400 300이며, 필요한 속도의 양의 정수배로 지역을 통과할 수 있다.
- 속도는 떨어뜨릴 수 있으며, 높일 수는 없다.
규칙이 위와 같으므로
지구에서 올려야 하는 속도를 900이라고 하면, 행성에 도달했을 때 속도는 다음과 같습니다.
900(300 * 3) - 800(400 * 2) - 500 - 400 - 300
그렇다면 어떻게 문제를 풀어가면 될까요?
지구에서 올려야 하는 속도를 저장하는 v_min 변수를 이용하여 풀 수 있습니다.
먼저, <필요한 속도> 리스트를 reverse하여 순회합니다.
필요한 속도의 가장 마지막 원소로 v_min을 저장합니다.
예시에선 5번째 원소인 300이 되겠습니다.
다음으로, <필요한 속도> 리스트를 순회하며
- v_min보다 <필요한 속도>가 크면 v_min을 <필요한 속도>로 업데이트합니다.
이유는 속도를 떨어뜨릴 수 있기 때문입니다.
예시를 보면 3번 ~ 5번 행성으로 이동할 때, 속도를 500 - 400 - 300으로 낮추는데요!
이처럼 저희는 v_min 값을 300 - 400 - 500순으로 업데이트해주는 겁니다. - v_min보다 순회값이 작으면
<필요한 속도> * (m-1) <= v_min < <필요한 속도> * m인 m을 찾은 다음
v_min 값을 <필요한 속도> * m으로 업데이트해줍니다.
(ex) 예시를 보면 2번에서 3번 행성으로 이동할 때 800 - 500으로 낮추는데요,
저희는 리스트를 reverse하여 뒤에서부터 최소 속도를 찾고 있으므로
3번에서 2번 행성으로 순회하며 "800"이란 값으로 v_min을 업데이트해야겠죠?
방법은 400 * 1 <= 500 < 400 * 2인 2를 찾아 400 * 2 = 800을 찾아주면 됩니다.
(ex) 2번에서 1번 행성으로 순회하는 상황도 마찬가지 인데요!
300 * 2 <= 800 < 300 * 3인 3을 찾아 300 * 3 = 900을 찾아주면 됩니다.
코드로는 v_min / <필요한 속도>를 올림하여 m을 찾아주면 됩니다.
import math
import sys
n = int(sys.stdin.readline())
v = list(map(int, sys.stdin.readline().split()))[::-1] # 행성 순서를 reverse
v_min = v[0]
for i in range(1, n):
if v_min == v[i]:
continue
elif v_min < v[i]: # 속도를 떨어뜨릴 수 있으므로
v_min = v[i]
else: # v[i] * (m-1) < v_min <= v[i] * m 인 m 찾기
m = math.ceil(v_min / v[i])
v_min = v[i] * m
print(v_min)
<필요한 속도> 리스트를 거꾸로 순회하며
v_min 값이 점점 커지도록 <필요한 속도> 양수배를 선택하는 그리디 알고리즘으로 볼 수 있습니다.
