[백준][파이썬] 13305번. 주유소

문제

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

 

풀이

첫 번째 시도

앞으로 남은 도시들과 비교했을 때 현재 도시의 가격이 가장 저렴하면 남은 거리를 갈 수 있을만큼 최대로 채우고, 그게 아니라면 다음 도시까지 이동할 만큼만 채우자.

• ex. 도시의 주유소 가격 : 5  2  4  1
  • 첫 번째 도시(가격 5) : 다음 도시로 이동할 만큼만 채우기
  • 두 번째 도시(가격 2) : 남은 도시(마지막 도시 제외) 중 가장 저렴한 가격이므로, 마지막 도시까지 갈 수 있을만큼 채우기

import sys
input = sys.stdin.readline

N = int(input())
length = list(map(int, input().split()))
price = list(map(int, input().split()))

price = price[:-1]
total = 0
dist = sum(length)
for i in range(len(length)) :
  if dist == 0 :
    break
  else :
    if price[i] == min(price[i:]) :
      total += price[i] * sum(length[i:])
      dist -= sum(length[i:])
    else :
      total += price[i] * length[i]
      dist -= length[i]
print(total)

결과 : 17점

두 번째 시도

질문 게시판을 참고한 결과 for문 안에서 매번 min(price[i:])를 계산하는 것이 문제라고 판단해서, for문 밖에서 미리 구하는 식으로 코드를 변경했다.

import sys
input = sys.stdin.readline

N = int(input())
length = list(map(int, input().split()))
price = list(map(int, input().split()))

price = price[:-1]
total = 0
dist = sum(length)
min_prices = min(price)  # 이 부분

for i in range(N-1) :
  if dist == 0 :
    break
  else :
    if price[i] == min_prices :
      total += price[i] * sum(length[i:])
      dist -= sum(length[i:])
    else :
      total += price[i] * length[i]
      dist -= length[i]
print(total)

결과 : 17점

• 반례
  • 도시의 주유소 가격 : 3  99  2  1
    • 첫 번째 도시 : 세 번째 도시까지 갈 수 있도록 기름을 충전해야 함
    • 두 번째 도시 : pass
    • 세 번째 도시 : 마지막 도시까지 갈 수 있도록 기름을 충전해야 함
  • 해당 반례를 기존의 내 코드로 풀면
    • 첫 번째 도시 : 두 번째 도시까지 갈 수 있도록 기름 충전
    • 두 번째 도시 : 세 번째 도시까지 갈 수 있도록 기름 충전
    • 이렇게 되어서 최소 가격을 구할 수 없음
• 결론 : 현재 위치에서의 기름값이 최소가 아니어도, 다음 도시보다 저렴하면 그 가격으로 충전해야 한다!!

세 번째 시도 (성공)

import sys
input = sys.stdin.readline

N = int(input())
length = list(map(int, input().split()))
price = list(map(int, input().split()))

total = 0
min_prices = min(price)

if price[0] == min_prices :
  sum_length = sum(length)
  total += price[0] * sum_length
  
else :
  total += price[0] * length[0]
  for i in range(1, N-1) :
    if price[i-1] < price[i] :
      price[i] = price[i-1]
    total += price[i] * length[i]
print(total)