[백준] 라면 사기 (Small)

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

18185번: 라면 사기 (Small)

 

i, i+1, i+2 공장에 라면이 있는 경우 7원으로 세 개의 라면을 사는 것이 가장 합리적이지만,

[1, 2, 1, 1] 의 경우 7원으로 사는 것을 우선적으로 사버리면 [0, 1, 0, 1] 로 다음 번에 무조건 하나씩 사게 되어 최소한의 가격으로 사지 못하는 경우가 발생한다.

[1, 2, 1, 1] 의 경우는 먼저 두 개의 공장에서 5원으로 라면을 산 뒤([0, 1, 1, 1]), 세 개의 공장에서 라면을 사는 것이 위의 경우보다 더 합리적이다.

 

즉, A[i+1] 이 A[i+2] 보다 큰 경우, 나중에 하나씩 사게 되는 경우를 막기 위해서 A[i+1] - A[i+2] 만큼은 두 묶음씩 사게 하며 A[i+1] 과 A[i+3] 이 같아질 때 세 개의 묶음으로 사는 것이 합리적이다.

 

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
answer = 0

for i in range(N-2):
    if A[i+1] > A[i+2]:
        m = min(A[i], A[i+1] - A[i+2])
        answer += m * 5
        A[i] -= m
        A[i+1] -= m
    
    if A[i] > 0 and A[i+1] > 0 and A[i+2] > 0:
        m = min(A[i], A[i+1])
        answer += m * 7
        A[i] -= m
        A[i+1] -= m
        A[i+2] -= m
    
    if A[i] > 0:
        answer += A[i] * 3
                
if A[-2] > 0 and A[-1] > 0:
    m = min(A[-2], A[-1])
    answer += (m * 5)
    A[-2] -= m
    A[-1] -= m

if A[-2] > 0:
    answer += (A[-2] * 3) 
else:
    answer += (A[-1] * 3)

print(answer)