백준 2156. 포도주 시식

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

틀린 처음 풀이

'''
연속으로 3잔 마실 수 없음! 2잔까지 가능
'''
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
arr = [int(input()) for _ in range(n)]
dp = [-1 for _ in range(n+1)]

def recur(idx, cnt):

    if idx >= n-1:
        return 0

    if cnt == 3:
        return dp[idx]

    if dp[idx] != -1:
        return dp[idx]

    # 먹었을 때와 안먹었을 때를 비교해서 더 큰 값 저장
    dp[idx] = max(recur(idx+1, cnt+1)+arr[idx], recur(idx+1, 0))

    return dp[idx]

print(max(recur(0,0)))

-> 어디서 문제가 생기는건지...cnt 처리하는 부분이 잘못된 것 같긴 한데 정확히 어딜 고쳐야될지 모르겠다.

1. 점화식 안 쓴 재귀+메모이제이션 풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
arr = [int(input()) for _ in range(n)]
dp = [-1] * n  # 메모이제이션 배열 (-1로 초기화)

def recur(idx):
    # 인덱스가 범위를 넘어가면 포도주 양은 0
    if idx >= n:
        return 0

    # 이미 계산된 경우 메모이제이션 값 사용
    if dp[idx] != -1:
        return dp[idx]

    # 현재 포도주를 마시는 세 가지 선택지 중 최댓값
    take1 = recur(idx + 2) + arr[idx]  # 1. 현재 잔만 마시고, 다음 포도주 건너뜀
    take2 = 0
    if idx + 1 < n:  # 2. 연속으로 두 잔 마시는 경우 (현재 잔 + 다음 잔)
        take2 = recur(idx + 3) + arr[idx] + arr[idx + 1]
    skip = recur(idx + 1)  # 3. 현재 잔을 건너뛰는 경우

    dp[idx] = max(take1, take2, skip)  # 최댓값 저장
    return dp[idx]

print(recur(0))

2. 점화식 풀이(정석? 풀이)

n = int(input()) # 포도주 잔의 개수

data = [0] * 10001
for i in range(1, n + 1):
    data[i] = int(input()) # 포도주의 양

dp = [0] * 10001 # 최대 포도주 양을 저장할 list
dp[1] = data[1]  # 1번째 값은 첫번째 포도주의 양
dp[2] = data[1] + data[2] # 2번째 값은 첫번째, 두번째 포도주 양의 합

for i in range(3, n + 1): # 3번째부터 반복
    # 현재 포도주를 마시지 않았을 경우, 현재 포도주와 이전 포도주를 마셨을 경우, 마시지 않았을 경우를 비교
    dp[i] = max(dp[i - 1], data[i] + data[i - 1] + dp[i - 3], data[i] + dp[i - 2])

print(max(dp)) # 구한 dp 중 최댓값 출력

"세 가지" 경우의 수를 고려해야된다!

1. 마심+마심+안마심 ~~

2. 마심+안마심 ~~

3. 안마심 ~~