악곱 == 악성곱슬

DP

---

옛날에 풀었던 문제인데, 친구가 자기 코드가 맞았는데 틀렸다고 그래서 나도 한번 다시 풀게 되었다.

이 문제에서 유의해야 할 점이라고 한다면, 3칸 연속으로 먹을 수 없기 때문에

• O O X
• O X O
• X O O

이렇게만 있을 것이라고 판단의 오류(?)를 범할 수도 있다. 그러나

• O O X X O O

처럼 2칸을 건너뛰어야 하는 경우도 있다.

따라서 점화식은 아래와 같다

• f(i) = max( f(i-1), f(i-2) + wine(i), f(i-3) + wine(i-1) + wine(i) )

구현

---

import sys

# 다른 사람이 짠 dp 코드. 엄청 깔끔한데 어떻게 이런 생각을 할 수 있을지 잘 모르겠다..
# def solution(n):
#     a, b, c = 0, 0, 0
#     for w in wine:
#         a, b, c = max(a, b, c), a + w, b + w
#     return max(a, b, c)

def solution(n):
    if n < 3:
        return sum(wine)
    result = [0] * n
    result[0] = wine[0]
    result[1] = wine[0] + wine[1]
    result[2] = max(wine[0] + wine[1], wine[0] + wine[2], wine[1] + wine[2])
    # 점화식의 내용대로 구현, 0, 1, 2에 대한 인덱스는 예외처리
    for i in range(3, n):
        result[i] = max(
            result[i-3] + wine[i-1] + wine[i],
            result[i-2] + wine[i],
            result[i-1]
        )
    return result[-1]

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    wine = [int(sys.stdin.readline().rstrip()) for _ in range(N)]
    print(solution(N))