그리디 | 백준 13305 주유소

문제

 

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

 

그림과 같이 원 안쪽의 숫자는 주유소의 리터당 가격이고, 선 위의 숫자는 이동해야할 거리(km)이다.

1리터로 1km를 이동할 수 있다고 할 때, 제일 왼쪽 도시에서 오른쪽 도시까지 이동하는 최소비용을 구하여라

 

차에 기름이 없는 상태로 출발하여 첫번째 주유소에서는 다음 주유소까지 이동할 수 있는 양의 기름을 넣어야 한다.

 

 

입력

• 첫 번째 줄: 도시의 개수를 나타내는 정수 N
• 두 번째 줄: 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수
• 세 번째 줄: 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수

4
2 3 1
5 2 4 1

 

 

출력

• 왼쪽 도시에서 오른쪽 도시까지의 최소 비용

 

풀이

import sys
input = sys.stdin.readline
N = int(input().strip())
roads = list(map(int, input().split()))
prices = list(map(int, input().split()))

cheapest = prices[0]
total = 0

for i in range(len(roads)):
    if prices[i] < cheapest:
        cheapest = prices[i]
    total += cheapest*roads[i]

print(total)

 

 

그리디 문제

도시를 순차적으로 돌면서 거쳐 온 주유소 중 가장 저렴한 주유소의 리터당 가격을 cheapest에 저장한다.

cheapest * (이전 도시부터 현재 도시까지의 거리)를 total에 더한다.

 

1) 두 번째 도시에 도착했을 때 지나친 도시 중 가장 저렴한 주유소의 리터당 가격은 5

2) total += 5 * 2(이전 도시부터 현재 도시까지의 거리)

3) 세 번째 도시에 도착했을 때 지나친 도시 중 가장 저렴한 주유소의 리터당 가격은 2 

4) total += 2 * 3

5) 세 번째 도시에 도착했을 때 지나친 도시 중 가장 저렴한 주유소의 리터당 가격은 2

5) total += 2 * 1

6) 답은 18