보자 마자 계단 오르기문제와 똑같다고 생각했지만 계단 오르기는 무조건 마지막 계단을 밟아야 하는 반면, 포도주는 꼭 마지막을 안 마셔도 된다.

삼각형 내부의 모든 지점에 dp를 수행하던 방향에 따라 그 전 층의 자신과 인접한 지점의 값 중 큰 값을 추가한다.

가능한 경우를 부모노드가 1인 트리로 그려보면 규칙을 파악하기 쉽다.

n번째 계단 까지 얻을 수 있는 최대 점수를 구하기 위해 두 가지 경우를 살펴보겠다.

n-1번째 계단을 밟고 왔을 경우

이 경우는 주어진 조건에 의해 n-2계단을 밟으면 안되므로 무조건 n-3계단을 밟고 와야 한다.
따라서 n-3번째 계단 까지 얻을 수 있는 최대 점수 + n-1번 계단의 점수 + n번 계단의 점수가 n번째 계단까지 얻을 수 있는 최대 점수가 된다.

규칙이 헷갈리는데 요약하면 같은 색인 집이 연속되면 안 된다고 정리할 수 있다.
따라서 색(r, g, b)별로 n번째 집까지 색을 칠하는 비용의 최소값은 n - 1번째 집까지의 비용에서 현재 집의 색을 제외한 나머지 색 중 최소값이 될 것이다.

2n 크기의 직사각형은 2(n-1)크기의 직사각형에서 세로로 길쭉한 블럭 하나를 추가한 것과 같고 2(n-2)크기의 직사각형에서 가로로 길쭉한 블럭 두개를 쌓아서 추가하는 경우와 같다.
2(n-2)크기의 직사각형 역시 세로로 길쭉한 블럭을 두개 추가하면 2n크기인 직사각형이 되지만, 2(n-1)와 겹치는 경우가 발생하기에 제외한다.

시간 제한이 0.25초로 걸려있는 것이 정직하게 피보나치 돌리면 시간 초과가 뜬다는 것을 암시한 것인가.