😊 백준 13305 : 주유소

13305: 주유소

Greedy 네 번째 문제~!
이것도 간단한 문제였다.

📌 Try 1

import sys
sys.setrecursionlimit(10000000)

def next(curIdx, nextIdx, length):
    if nextIdx >= length:
        return 0
    
    curCost, nextCost = cost[curIdx], cost[nextIdx]
    curDis = distance[nextIdx - 1]
    Cost = curCost * curDis
    
    # 현재 값이 더 저렴할 때
    if curCost < nextCost:
        return Cost + next(curIdx, nextIdx + 1, length)
    else:
        return Cost + next(nextIdx, nextIdx + 1, length)

N = int(input())
distance = list(map(int, input().split()))
cost = list(map(int, input().split()))

sumCost = next(0, 1, len(cost))
print(sumCost)

재귀를 이용해서 풀었다.
N의 범위가 매우 크기 때문에 재귀 depth도 매우 크게 잡았다.

정당성 분석 :

현재 도시의 기름 값보다 기름 값이 저렴한 도시에 도착하기 전까지 필요한 기름을 현재 도시에서 채우면 최소 가격으로 도착할 수 있다.

🎯 다른 분 코드

N = int(input())
distance = list(map(int, input().split()))
cost = list(map(int, input().split()))
won = 0

h = cost[0]
for i in range(len(distance)):
    if cost[i] <= h:
        h = cost[i]
    won += h * distance[i]

print(won)

Other

min 함수를 이용해서 푸는 방법도 있다.

🎁 Reference

• 백준 13305번(python) - 주유소
  https://dortmund.tistory.com/129