[알고리즘] 백준 13305번_주유소 문제풀이 (Python, 파이썬)

 

13305번: 주유소

 

문제

제일 왼쪽 도시에서 제일 오른쪽 도시로 이동할 때 1km당 1리터의 기름을 사용한다.

각 도시에서 리터당 주유 가격이 주어지고 인접한 도시 사이의 길이(km)가 주어졌을 때

최소한의 금액으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동할 때 어떻게 주유를 해야하는가

(기름이 0으로 시작하기 때문에 무조건 가장 왼쪽 도시에서는 주유하고 시작)

 

구하고자 하는 것

제일 왼쪽 도시에서 제일 오른쪽 도시로 이동할 때 주유하는데 필요한 최소 금액

 

입력

도시의 개수 N

인접한 두 도시 간의 길이 (N-1개의 자연수)

해당 도시의 1리터 당 주유 가격 (N개의 자연수)

 

IDEA

지금 내가 있는 도시의 주유 가격이 바로 다음 도시의 주유 가격보다 비싼 경우 다음 도시에 가서 주유하는 것이 이득

그렇다면 ..

지금 내가 있는 도시의 주유 가격과 바로 다음 도시의 주유 가격을 비교해야 하는데

 

• 내가 첫번째로 생각했던 방법 : 인덱스 i, i+1 비교해서 더 작은 값을 거리와 곱하기
• 문제점
  • 무조건 주유를 하고 출발하기 때문에 0번째 도시의 주유값이 1번째 도시의 주유값보다 비싼 경우 성립 X
  • 0번째 인덱스의 도시와 거리를 곱해서 ans값의 초기화 값으로 사용한다고 하더라도,
    그 후 i, i+1번째 주유 가격을 비교할 때 i번째의 주유가격이 i+1 이후 번째의 도시의 주유가격보다 저렴할 수 있음

 

해결책 : 해당 도시에 오기까지의 최소 주유 금액을 새로운 변수에 저장해서 사용하자.

(최솟값 구하는 알고리즘에서 두 개씩 비교하고 작은 값을 계속 임시 변수에 저장해놓는 st..처럼)

(이렇게 하면 첫번째 대상은 무조건 최솟값이 되도록 가질 수 있는 최댓값보다 더 크게 설정하면 된다.)

 

• 가장 처음의 도시에서는 무조건 주유를 하고 가야하기 때문에 첫번째 도시의 주유가격과의 비교대상(temp)은 
• 첫번째 주유가격과 비교하는 값은 항상 주유가격의 범위인 1,000,000,000보다 크게 설정
• 그리고 temp값을 n번째 도시의 주유값과 비교해 가면서 작은 값으로 계속 업데이트 시키면 된다.
• 마지막 주유 가격은 전체 금액에 영향을 주지 않기 때문에 해당 반복은 N-1번 반복

 

Code

N = int(input())

dist = list(map(int, input().split()))
cost = list(map(int, input().split()))

temp = 1000000001
ans = 0

for i in range(N-1):
    if cost[i] <= temp:
        temp = cost[i]
    ans += temp * dist[i]

print(ans)