n이 최대 15이기 때문에 최악의 경우에도 2^15가지의 경우의 수를 가진다.
따라서 완전탐색을 해도 문제가 없다.
하지만 동적 계획법으로도 해결할 수 있기 때문에 두가지 방법을 다뤄보겠다.

좀 생각 많이 한 문제다.
카드 n개를 구매할 때 최대 금액은 카드 n - j개를 구매할 때의 최대 금액 + 카드 j개가 담겨있는 카드팩의 가격일 것이다.
카드팩의 가격은 arr[]에 저장하고 카드 n개를 가장 비싸게 구매할 때 금액을 dp[n]에 저장한다면, 카드 n개를 가장 비싸게 구매할 때 금액은 dp[n], dp[n - 1] + arr[1], dp[n - 2] + arr[2], dp[n - 3] + arr[3]…dp[n - n] + arr[n] 중 가장 큰 값이 된다.

문제에서 주어진 그림을 보면 점화식을 세울 수 있다.
i번째 삼각형의 변의 길이는 i-1번째 삼각형의 변의 길이 + i - 5번째 삼각형의 변의 길이와 같다.

숫자 i 다음 으로 나올 수 있는 수는 i-1과 i+1이다.
하지만 0과 9는 다음으로 나올 수 있는 수가 각각 1과 8이다.
이 부분에 대해 예외처리를 하려 했으나 dp가 전역으로 정의돼있기 때문에 필요가 없었다.

합이 가장 큰 연속된 부분집합을 찾는 문제로 dp[i - 1] + i번째 수와 i번째 수 중 큰 것을 dp[i]에 저장한다.

1. dp[i - 1] + i번째 수
2. i번째 수

1번이 더 크다면 dp[i - 1]가 양수고, 2번이 더 크다면 dp[i - 1]가 음수다.

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

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

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

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

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

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

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