백준 13305번 - 주유소

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

# 틀린코드

그리디 알고리즘 개념을 적용해보면 기름값이 제일 싼 곳에서 많이 넣고, 비싼 곳에선 필요한만큼만 넣는다. 그래서 최솟값의 index를 찾아 최솟값이 아닌 경우는 필요한 경우만 넣고 최솟값에서 기름 가득 넣고 출발하였다. 엥 17점? 반례를 찾아보니 최솟값을 만나기 전에 더 비싼 주유소에서 기름을 넣게 된다. 한마디로 예외처리가 덜 되서 다시 품ㅎㅎ

import sys

input = sys.stdin.readline

N = int(input())
roadDistance = list(map(int, input().split()))
pricePerL = list(map(int, input().split()))
price = 0

minPriceIndex = pricePerL.index(min(pricePerL[:-1]))

idx = 0
while idx < N:
  if idx == minPriceIndex:
    price += pricePerL[minPriceIndex] * sum(roadDistance[idx:])
    break
  if pricePerL[idx] < pricePerL[idx+1]:
    price += pricePerL[idx] * sum(roadDistance[idx:minPriceIndex])
    idx += minPriceIndex - idx
  else:
    price += pricePerL[idx] * roadDistance[idx]
    idx += 1

print(price)

# 정답코드

예외를 처리하니 정답처리가 되었다. 하지만 코드가 뭔가 난잡하다. 변수도 많도 if문도 줄일 수 있을 거 같이 너무 많음. 시간복잡도도 O(N)*O(k)? 맘에 안드는데 다른 방법이 없을까?

import sys

input = sys.stdin.readline

N = int(input())
roadDistance = list(map(int, input().split()))
pricePerL = list(map(int, input().split()))
price = 0

minPriceIndex = pricePerL.index(min(pricePerL[:-1]))

idx = 0
end = 0

while idx < N:
  if idx == minPriceIndex:
    price += pricePerL[minPriceIndex] * sum(roadDistance[idx:])
    break
  if pricePerL[idx] <= pricePerL[idx+1]:
    while pricePerL[idx] <= pricePerL[end]:
      end += 1
    price += pricePerL[idx] * sum(roadDistance[idx:end])
    idx += end - idx
  else:
    price += pricePerL[idx] * roadDistance[idx]
    idx += 1
  end = idx

print(price)

# 참고코드

최솟값을 미리 계산할 필요도 없었고 index를 2개나 쓸 필요도 없었고 난잡한 if문들도 사라졌다. 한번에 처리한다고 코드가 깔끔해지는 게 아니였다. 순서대로 하나씩 체크하는 게 가장 깔끔한 문제였다. 선택정렬할 때처럼 최솟값을 첫번째값으로 정해두고 for문 돌면서 더 작은값이 있으면 최솟값으로 채택하여 계산한다. 각각의 도시에서 최소비용을 계산하여 지나가는, 완벽히 그리디 알고리즘이 적용된 코드다.

def solution(cities, distance, price):
    cost = 0
    min_cost = price[0]
    for i in range(cities-1):
        if price[i] < min_cost:
            min_cost = price[i]
        cost += min_cost * distance[i]
    return cost

cities=int(input())
distance = list(map(int,input().split()))
price=list(map(int,input().split()))
print(solution(cities,distance,price))