[백준 온라인 저지] 주유소

문제 출처

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

13305번: 주유소

 

문제 요구사항

• N개의 도시가 수평으로 존재하는 어떤 나라에서 수평의 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 차를 타고 이동
• 인접한 두 도시 사이의 도로를 이동할 때 1Km마다 1L의 기름을 사용
• 최초 출발시에는 기름이 없어서 주유소에서 기름을 넣고 출발
• 각 도시에는 단 하나의 주유소가 존재하며, 리터당 가격이 도시마다 다를 수 있음
• 제일 왼쪽 도시에서 제일 오른쪽 도시를 이동하는데 사용하는 기름의 비용을 최소화 하도록 구성

 

나의 풀이(Python3)

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

# 초기 자동차에 기름을 주유해야함
# 기름통의 크기는 무제한
# 이동시 1Km마다 1리터의 기름을 사용
# 각 도시마다 주유소가 하나씩 존재
# N = 도시의 갯수
import sys

N = int(sys.stdin.readline().strip()) # 도시의 수
city_dis = list(map(int, sys.stdin.readline().strip().split()))
gas_cost = list(map(int, sys.stdin.readline().strip().split()))

answer = 0
min_cost = 1000000001
for i in range(0, len(gas_cost)):
    if min_cost > gas_cost[i]:
        min_cost = gas_cost[i]
    
    if i < len(city_dis):
        answer += min_cost * city_dis[i]

print(answer)

 

 

 

 

• 비용을 최소화 시키기 위해서는 주유소의 리터당 가격이기 때문에 각 도시별 기름 비용을 순서대로 탐색하면서 최소의 비용을 계산
  • 최초 기름 비용을 최댓값으로 설정
  • 반복을 진행하면서 기름 비용이 최소인지 확인
  • 도시를 이동하면서 최소 기름 비용과 거리의 곱셈으로 답안을 도출

 

Github

• https://github.com/Limseunghyun95/Algorithm_study/blob/master/baekjoon/p_13305.py