[백준] 13305.주유소/Python - Silver3

❓문제

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

성능 요약

메모리: 46228 KB, 시간: 112 ms

 

문제 설명

어떤 나라에 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원이다.
각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

✍🏻풀이

우리는 제일 오른쪽 도시까지 가는 데 최소 비용으로 주유해야 한다.
제일 왼쪽 도시의 주유소의 가격이 최소값이라고 생각했을 때 총 30이 나온다.
모든 경우를 고려하여 계산했을 때 5x2 + 2x(3+1)일 때가 18로 가장 적다.
이동하기 위해서는 첫 주유소에서는 무조건 주유를 해야 한다. 그러므로 dp[0]은 첫 주유소 가격 * 도로 길이이다.
그 다음 주유소에서는 이전 주유소 가격과 비교했을 때 최소 가격을 골라 계산한다.
이전 주유소는 5이고 현재 도시의 주유소는 2이다. 그러므로 2를 택한다.
그 다음 도시는 4로 이전 도시의 가격이 더 적다. 따라서 2x1을 더한다.
이 같은 방법으로 가장 오른쪽 도시에 도착할 때까지 최소 가격 * 도로 길이를 하여 최소 비용을 구한다.

💻코드

# 서브태스크 1 성공(이전 주유소의 가격하고만 비교)
import sys

input = sys.stdin.readline

n = int(input())
lengths = list(map(int, input().split()))
prices = list(map(int, input().split()))
dp = [0] * (n - 1)
dp[0] = lengths[0] * prices[0]

for i in range(1, n - 1):
    dp[i] = dp[i - 1] + min(lengths[i] * prices[i], lengths[i] * prices[i - 1])

print(dp[n - 2])

# 정답 코드
import sys

input = sys.stdin.readline

n = int(input())
lengths = list(map(int, input().split()))
prices = list(map(int, input().split()))
dp = [0] * (n - 1)
dp[0] = lengths[0] * prices[0]

minCost = prices[0]
for i in range(1, n - 1):
    if minCost > prices[i]:
        minCost = prices[i]
    dp[i] = dp[i - 1] + minCost * lengths[i]

print(dp[n - 2])

📍후기

경우의 수를 따져놓고 이전 주유소의 가격하고만 비교하여 서브태스크 1만 통과했다. 주어진 테스트 케이스를 보았을 때 결과가 같아서 맞다고 생각했지만 코드를 다시 보니 경우의 수를 제대로 고려하지 못했다는 것을 깨달았다. 제발 문제 제대로 읽고 여러 번 생각하자😂