[BOJ] 2156번 - 포도주 시식

---

문제설명

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

2156번: 포도주 시식

사고과정

• 연습장에 그려가며 규칙을 발견하려고 했다. 다음 포도주의 입장에서 생각하여 N번째 포도주를 마실 경우와 마시지 않을 경우를 생각해보았다. 그런데 연속해서 3잔이상은 못마신다는 조건 때문에 약간 복잡해졌다.. 그래서 포도주 array 따로 DP 테이블 따로 1차원 리스트를 2개로 운영해야 할 것 같았다.. N = 4일때까지 경우의 수를 구했음에도 점화식이 헷갈렸다.. 포도주 array를 참조해야 하는지 DP 테이블을 참조해야 하는지..
• 풀지 못하고 풀이를 보니 생각하는 점화식과 거의 비슷했지만 정답 규칙을 파악하진 못했다. 규칙을 도식화해보면 다음과 같다.

 

위 테이블을 참고로 하여 점화식을 세우게 되면 $$DP[i] = max(DP[i-1], DP[i-2] + array[i], DP[i-3] + array[i-1] + array[i])$$가 된다. 개인적인 생각으로는 N = 4일 때보다 더 확실하게 세우기 이해 N = 5, 6, 7 일때까지 더 경우의 수를 탐색하는 게 좋을 듯하다.. N = 4일 때 바로 규칙을 알아차린다면 눈치 백단일듯.. 참고로  N이 1 또는 2일때 개별 처리해주는 것도 잊지말자!

풀이(스스로 못 푼 풀이)

n = int(input())
array = [int(input()) for _ in range(n)]
if n == 1 or n == 2:
    print(sum(array))
else:
    dp = [0] * n
    dp[0] = array[0]
    dp[1] = array[0] + array[1]

    for i in range(2, n):
        dp[i] = max(dp[i-1], dp[i-2] + array[i], dp[i-3] + array[i-1] + array[i])

    print(dp[n-1])