백준(baekjoon) 13305번: 주유소(실버 3, 파이썬 PYTHON) - 그리디 알고리즘

문제

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다. 

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

 

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

13305번: 주유소

 

import sys

N=int(sys.stdin.readline())
dist=list(map(int,sys.stdin.readline().split()))
cost=list(map(int,sys.stdin.readline().split()))
min_cost=0
oil_cost=cost[0]

for x in range(len(cost)-1):
  if(oil_cost<=cost[x]):
    min_cost+=oil_cost*dist[x]
  else:
    oil_cost=cost[x]
    min_cost+=oil_cost*dist[x]

print(min_cost)

 

※ 그리디 알고리즘

 

 

● 먼저 도시의 개수 N을 입력받은 뒤, 인접한 두 도시를 연결하는 도로의 길이를 나타내는 N-1개의 자연수를 dist 배열에 저장하고, 주유소의 리터당 가격을 나타내는 N개의 자연수를 cost 배열에 저장해준다. 그리고 최소 비용을 계산할 0으로 초기화 된 변수 min_cost 와 초기값이 cost[0]인 변수 oil_cost를 선언해준다.

 

● for문의 x는 0부터 cost 배열 길이-2 까지의 값을 가진다(마지막 cost배열 원소는 맨 끝 주유소의 가격이므로 고려 안해줘도 됨). 만약 현재 보고있는 주유소의 가격이 현재 oil_cost에 저장되어 있는 가격보다 크거나 같으면(oil_cost<=cost[x]), dist[x]의 거리는 oil_cost의 가격으로 주행하는 것이 최소 비용을 쓰는 방법이므로, min_cost에 oil_cost * dist[x] 값을 더해준다.

 

● 만약 현재 보고있는 주유소의 가격이 현재 oil_cost에 저장되어 있는 가격보다 작으면, 현재 보고있는 주유소의 가격으로 다음 거리를 주행하는 것이 최소 비용을 쓰는 방법이므로, oil_cost를 cost[x]로 갱신해준 뒤 min_cost에 oil_cost * dist[x] 값을 더해준다.

 

● for문을 빠져나온 뒤 min_cost 값을 출력해주면 답을 구할 수 있다.