[백준 13305번] 주유소 - 파이썬

https://www.acmicpc.net/problem/13305

13305번: 주유소

 

💡문제 분석 요약

N개의 도시가 있고, 도시 사이에는 거리가 있다.

각 도시에는 주유소마다 기름의 가격이 다른데, 가장 싸게 기름을 충전하여 첫 도시에서 마지막 도시까지 갔을 때의 기름 값을 구하여라.

 

💡알고리즘 설계

1. 첫 도시에서 다음 도시까지 가기 위한 기름을 구매한다.

2. 첫 도시의 기름값을 가장 싼 기름값으로 저장한다.

3. 다음 도시의 기름 값과 이전에 저장된 가장 싼 기름값의 가격을 비교해, 더 싼 기름으로 다다음 도시까지 가기 위한 기름을 구매한다. 이를 마지막 도시에 도착할 때 까지 반복한다.

 

💡코드

N=int(input())

dist_list=list(map(int, input().split()))
city_list=list(map(int, input().split()))

money=0
min_city=city_list[0]

for i in range(N-1):
    if city_list[i]<min_city:
        min_city=city_list[i]
    money+=min_city*dist_list[i]

print(money)

 

💡시간복잡도

O(n)

 

💡 느낀점 or 기억할 정보

dp문제인데 dp보다 직접 구현하는게 더 빠를 것 같아 직접 구현해서 풀었다.

생각보다 빠르게 풀려서 놀랐는데, 정작 dp로 푸는 방법은 생각이 나지 않는다.. ^^;

dp로 푸는 방법도 연구해보고 싶다.