보자마자 떠오른것은 조합이다.
mCn을 계산하면 정답이 나오지만 m이 최대 29까지 등장하기 때문에 계산 과정에서 29!을 계산할 여지가 있다.
29!은 long long에도 못들어가는 아무튼 엄청 크다.
이를 해결하는 방법은 여러가지가 있다.

동적 계획법으로 해결할 수 있다.

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]가 음수다.