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

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

18185번: 라면 사기 (Small)

라면 사기 (Small) 문제

공장에서 라면을 구매할 경우 어떻게 사면 제일 싸게 살 수 있는지 찾는 문제

약간의 함정을 조심한 그리디로 풀 수 있었다

📌문제 접근 포인트

1. 단순하게 생각해 보자, 3개를 연속하게 사야 하면 그때 사고, 그다음에 2개를 연속하게 사야 하면 그때 사고, 그다음에 1개를 사도록 구성해 주면 해결될 것 같다.
2. 중간에 함정이 숨어있다. 2, 3, 2, 1과 같은 경우 3 → 2 → 1의 순서로 따라갈 경우
1 2 1 1 → 7원
0 1 0 1 → 14원
0 0 0 1 → 17원
0 0 0 0 → 20원
20의 결과가 나오지만, 3개 연속이 아닌 2개 연속을 먼저 진행하면 19의 결과를 얻을 수 있다.
1 2 2 1 → 5원
0 1 1 1 → 12원
0 0 0 0 → 19원
즉 최솟값이 달라진다.
3. 위 케이스의 경우 2개 연속해서 사는걸 2번 반복 후 진행하는 게 아닌 1번만 하고, 3개를 사는 형태로 구성이 되어있다. 이 횟수는 i+2번과 i+1번의 차이만큼만 2번 산다는 것을 알 수 있다.
4. 3번의 경우를 고려해서 1번의 형태로 그리디 하게 구현하면 쉽게 해결할 수 있다. 

⚙️내가 푼 정답 코드

def buy1(n): # 1개 살 경우
    global result
    result += 3 * x[n]

def buy2(n): # 2개 살 경우
    global result
    m = min(x[n:n+2])
    x[n] -= m
    x[n+1] -= m
    result += 5* m    

def buy3(n): # 3개 살 경우
    global result
    m = min(x[n:n+3])
    x[n] -= m
    x[n+1] -= m
    x[n+2] -= m
    result += 7* m
    
import sys
N = int(sys.stdin.readline())
x = list(map(int, sys.stdin.readline().split())) + [0,0]
result = 0
for i in range(len(x)-2):
    if x[i+1] > x[i+2]: # # 3번째가 더 작으면 -> [2, 3, 2, 1] 같은 케이스
        m = min(x[i], x[i+1] - x[i+2]) # x[i]랑 x[i+1]-x[i+2] 비교
        x[i] -= m
        x[i+1] -= m
        result += 5*m # 이 때는 3곳보단 2곳 사는게 이득
        buy3(i) # 남는 갯수는 3곳에서 사자
        buy1(i) # 마지막 남은건 그냥사자
    else :
        buy3(i)
        buy2(i)
        buy1(i)
print(result)