[백준 13305번] 주유소

import sys
input = sys.stdin.readline

# n 입력받기
n = int(input())

# 총 비용
total = 0

# n-1개의 거리를 저장하는 리스트
distance = list(map(int,input().split()))
# 주유소의 리터당 가격을 저장하는 리스트
price = list(map(int,input().split()))

# 남은 거리 수
remain = sum(distance)

# 현재 최소 거리
min_price = price[0]
# 현재 누적된 거리
sum_distance = distance[0]

for i in range(n-1):
    if i == n-2:
      total += (sum_distance * min_price)
      break
  
    if min_price <= price[i+1]:
        sum_distance += distance[i+1]
    else:
        remain -= sum_distance
        total += (sum_distance * min_price)
        min_price = price[i+1]
        sum_distance = distance[i+1]

print(total)

이번 문제는 전형적인 Greedy 문제였는데, 처음에는 부분점수 17점만 맞게 되길래 예외처리를 하지 못한 부분이 있다고 생각했었는데, 질문 게시판에 올라온 반례를 보고나서 내 코드에 실수가 있었다는 것을 알 수 있었다.

 

먼저 본인이 생각한 로직은 이렇다.

1. 최소 비용이라는 변수(min_price)을 유지한 채로, 주유소 비용이 더 작은 주유소를 만나기 전까지는 그 비용을 사용하여 주유를 한다.

2. 만약에 주유소 비용이 더 비싼 주유소를 만난다면 비용은 유지한 채로 주유한다.

 

알고보니 위 로직에서 가격을 비교하는 과정에서 현재 까지의 최소 비용(min_price)와 다음 주유소의 거리(price[i+1])를 비교했어야 했는데, price[i]와 price[i+1]을 비교하는 바람에 예외가 발생한 것 이었다,,

 

결국 이 문제의 핵심은 최소의 비용만을 사용해서 주유를 하는 것이다 !

 

따라서 위 방법처럼 복잡하게 풀 이유가 없고, 최소의 비용을 유지하면서 (거리 * 최소 비용)을 총 비용에 더해주는 과정을 반복해주면 되었던 것이다.

import sys
input = sys.stdin.readline

# n 입력받기
n = int(input())

# n-1개의 거리를 저장하는 리스트
distance = list(map(int,input().split()))
# 주유소의 리터당 가격을 저장하는 리스트
price = list(map(int,input().split()))

# 총 비용
total = 0

min_price = price[0]

for i in range(n-1):
    if price[i] < min_price:
        min_price = price[i]
    total += min_price * distance[i]

print(total)

👉🏻 개선된 Python 코드

 

뒤에 가격이 비싼 주유소를 들리기전에 미리 주유해야 한다는 생각 때문에 쉽게 떠올리긴 힘들었지만, 그리디하게 접근하는 방식을 좀 더 고민해볼 수 있는 좋은 문제였다 :)