백준 17451(평행 우주) - Python(파이썬) - 그리디 알고리즘

17451번: 평행 우주

예제 풀이

연산은 마지막 행성부터 시작한다. - ( 속도의 최솟값을 구할 때 마지막 지구에 도착할 땐느 그 행성의 속도와 동일한 값이면 되기 때문 )

 

마지막 행성부터 시작해서

1️⃣ 현재 속도( result )가 행성 이동시 필요한 최소 속도( vi )보다 작거나 같은 경우 ( result < vi ) : result = vi 

2️⃣ 현재 속도(result)가 행성 이동시 필요한 최소 속도보다 큰 경우에 행성 속도가 양의 배수가 아닌 경우 ( result > vi  ) 

  : (행성 이동시 필요한 최소 속도를 현재 속도로 나눈 몫을 구한 후 +1 ) 을 한 값에 필요한 최소 속도를 곱한다. 

    (vi  // result +1 ) * vi  을 해주어서 vi 보다 크고 vi 의 양의 배수로 만들기

행성번호	1	2	3	4	5
행성 이동 시 필요한 최소 속도(v)	300	400	500	400	300
행성의 속도	900 ( 2️⃣ 최소 속도가 800보다 작으므로 { (800 //300)+1 }X300 = 900 )	800 ( 2️⃣ 최소 속도가 500보다 작으므로 {(500//400)+1} X 400 = 800 )	500 (1️⃣ 최소 속도가 400보다 크므로 최소 속도 500으로 만들기)	400 (1️⃣ 최소 속도가 300보다 크므로 최소 속도 400으로 만들기)	300
	⬅️	⬅️	⬅️	⬅️

즉, 900부터 시작해서 줄여 나가면서 300으로 지구에 도착하면 된다.

 

문제 풀이

① 현재의 속도가 vi보다 작은 경우 : result = vi
② 현재의 속도가 vi보다 큰 경우 : result =  (result // vi + 1 ) * vi

💻 Python( 파이썬) 

import sys
n = int(sys.stdin.readline())
v = list(map(int,sys.stdin.readline().split()))
#역순으로 진행해야하므로
v.reverse()

result =0
for i in v:
	#vi보다 작거나 같은 경우
    if result<=i:
        result = i
    #vi보다 큰 경우 vi의 배수가 아닌 경우 -> True 
    #result%i > result%i!=0와 동일
    if result%i:
        result = (result // i+1)*i

print(result)