[그리디 알고리즘] ▲ 13305번 - 주유소(완전탐색)

[백준] 13305번 - 주유소

1) 문제 해결 아이디어

아이디어를 떠올리는 것은 어렵지 않았으나 이것을 수식화하는 것이 좀 오래걸렸다.

여기서 핵심은 현재까지 최소 가격보다 더 작은 값의 가격이 나타나면 최소가격(target)을 갱신하는 것이다. 비용(cost)는 거리(distance[i])에 가격(price[i])을 곱한 값으로 계산한다.

 

2) 소스코드

n = int(input())  # 도시 수
distance = list(map(int, input().split()))  # 도시 간 거리(n-1 개)
price = list(map(int, input().split()))  # 리터당 가격(n 개)

cost = 0     # 총 비용
target = 1e9 # 현재까지 최소 가격
for i in range(n-1):
  # 현재 가격이 현재까지 최소 가격이 보다 작으면
  if(target > price[i]):
    # 최소 가격 갱신
    target = price[i]
  cost += distance[i] * target  # 최소 가격으로 계산
    
print(cost)