[python] 백준 18185 라면 사기 (small)

 

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

18185번: 라면 사기 (Small)

 

문제 해결

• 단순히 3개를 많이 사고 2개 1개를 사면 좋을거라 생각하기 쉽다.
• 하지만 j, j+1, j+2 공장 라면이 만약  3 5 2 로 있다고 생각해보자.
  • 3개를 먼저 사면 7*2 + 5*1 + 3*2 = 25일 것이다.
  •  j+1,j+2공장 차이만큼 j와 j+1공장에서 라면을 먼저 사도 5*3 + 5*2 =  25이다.
  • 하지만 j+3 고장에 만약 2개가 있다면?
  • 3개를 먼저 사는 전략이면 7*2 + 5*1 + 3*2 + 3*2 = 31 이다. (계산해보면 알겠지만 다음거에서 할인을 못받는다.)
  • 하지만 j+1,j+2공장 차이만큼 j와 j+1공장에서 라면을 먼저 사면 5*3+7*2 = 29로 더 싸다.
  • 즉 다음거를 생각하면 j+1과 j+2공장의 차이와 j공장 중 최솟값만큼 2개 묶음을 먼저 사는 것이 더 좋다는 것이다.
• 직접 다음 공장의 라면을 고려하며 생각하지 않으면 생각하기 힘든 문제라고 생각한다.

 

CODE

import sys
input = sys.stdin.readline

def buy_three(i):
    global answer
    k = min(A[i:i+3])
    A[i], A[i+1], A[i+2] = A[i]-k, A[i+1]-k, A[i+2]-k
    answer += 7*k
def buy_two(i):
    global answer
    k = min(A[i:i+2])
    A[i], A[i+1] = A[i]-k, A[i+1] -k
    answer += 5*k
def buy_one(i):
    global answer
    answer += 3*A[i]
if __name__=='__main__':
    n = int(input())
    A = list(map(int, input().split())) + [0,0] # for문으로 한번에 돌리기 위해서
    answer = 0
    for j in range(n):
        if A[j+1] > A[j+2]:
            k = min(A[j],A[j+1]-A[j+2])
            A[j], A[j+1] = A[j] - k, A[j+1] - k
            answer += 5*k
            buy_three(j)
        else:
            buy_three(j)
            buy_two(j)
        buy_one(j)
    print(answer)