무려... 3년전에 3개월동안 고생하다가 못 풀고 입대 후,
전역 하고 풀었다... 가히 인간승리가 아닐 수 없다.
[풀이]
머릿속에 맴돌던 아이디어는 딱 하나다. 아 이거 napsack dp같은데...
dp테이블 하나의 값을 얻기 위해 필요한 정보는 1.현재 남은 날짜, 2.이제 선택할 레벨의 캐릭터, 3.남은 현재 선택할 레벨 캐릭터의 개수
라고 생각했다.
$n$이 매우 작으니 dp table을 이렇게 구성해보았다.
$dp[i][j][k]$는 $i$일 남았고, $j$레벨을 선택할 때, $k$개의 "더"캐릭터가 있을 때 "더" 얻을 수 있는 최대 레벨
로 구성했다. 여기서 "더"를 강조한 이유는, 문제에서 처음에 각 캐릭터가 얼마나 주어질지 언급이 없기 때문에,
dp table에 그냥 캐릭터수를 넣어버리면 위 사진처럼 런타임에러가 난다.
dp table을 정의햇으니, 점화식을 세워보면
$dp[i][j][k] = dp[i - idx][j + 1][idx] + (power[j + 1] - power[j]) * idx$로 세울 수 있다.
정말 간단한 생각이니 설명이 없어도 충분히 이해하리라 믿는다.
내가 이걸 rank매긴다면 실버 1~2정도로 매길 것 같다. dp table이 3중이라 그렇지 정말 간단한 생각만 하면 풀리기 때문에...
근데 다른 사람들은 dp table을 1차원으로 짯던데 어떻게 그렇게 짯는지 한번 봐야겠다.
