[코테] 백준 그리디 18185번 문제

18185번 : 라면 사기 (Small)

문제 링크

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

문제 설명

라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i ≤ N).

교준이는 아래의 세 가지 방법으로 라면을 구매할 수 있다.

1. i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다.
2. i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 5원이 든다.
3. i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-2). 이 경우 비용은 7원이 든다.

최소의 비용으로 라면을 구매하고자 할 때, 교준이가 필요한 금액을 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 라면 공장의 개수를 의미하는 자연수 N가 주어진다.

두번째 줄에 N개의 정수 A1, ···, AN가 사이에 공백을 두고 주어진다.

출력

첫 번째 줄에 교준이가 필요한 최소 금액을 출력한다.

문제 풀이

2시간 정도 고민하다가 해결을 못해서 결국 인터넷 검색을 통해 해결했다…

핵심은 i, i+1, i+2의 라면을 구매할 때 i+1 > i+2 인 경우를 분리해서 해결해야한다는 점이다.

N = int(input()) 
An = list(map(int, input().split())) + [0, 0]  
cost = 0

def f(d, m, s):
    global cost
    for i in d:
        An[i] -= m
    cost += s * m

for i in range(N):
    if An[i+1] > An[i+2]:
        f([i, i+1], min(An[i], An[i+1] - An[i+2]), 5)
        f([i, i+1, i+2], min(An[i:i+3]), 7)
        f([i], An[i], 3)
    else:
        f([i, i+1, i+2], min(An[i:i+3]), 7)
        f([i, i+1], min(An[i], An[i+1]), 5)
        f([i], An[i], 3)
    An[i] = 0

print(cost)