[백준] 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을 만족한다.

 

📑출력

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

 

📚 문제 해석

문제를 이해하는데 약간 시간이 걸린 문제였다.

정리해보자면,,,

행성마다 각 속력이 정해져있고 그 행성을 지날때는 그 정해진 속력의 양의 정수 배로만 지나가야 한다.

출발할 때 속력은 정해져있다.

출발 이후 속력을 떨어뜨릴 수 있지만 올릴 수는 없다.

 

문제를 이해하고 나니 풀이법은 쉽게 떠올랐다.

처음 speed 는 가장 마지막 데이터로 두고, 역방향 순차 탐색을 한다.

 

만약 현재 스피드가 행성 속력(v)보다 낮다면 현재 스피드를 행성 속력(v)으로 업데이트 한다.

이 경우는 정방향으로 갈때 속력을 떨어뜨린 경우이다.

 

현재 스피드가 행성 속력(v)보다 높은 경우에는 정수 배가 되는 지 체크해야한다. 만약 정수배가 된다면 그냥 넘어가도 되지만 정수배가 되지 않는다면 스피드를 올려 정수배를 맞춰야 한다.

 

 

💻 코드

n = int(input())
nums = list(map(int,input().split()))
speed = nums[-1]

for i in range(n-2, -1, -1): # 뒤에서 두번째부터 역순으로
    if nums[i] > speed: # speed보다 행성 속력이 크다면
        speed = nums[i] # speed를 현재 행성 속력으로 업데이트
    else: speed가 더 크거나 작다면
        if speed%nums[i]: # 정수배가 되지 않는다면 
            speed = (speed//nums[i]+1) *nums[i] # 배수이면서 최소값으로 업데이트
print(speed)

 

 

🔗 문제링크 평행 우주

17451번: 평행 우주

 

평행우주