BOJ 2728 - 오늘은 마가리타 한 잔?

BOJ 2728 - 오늘은 마가리타 한 잔?

안 산 마가리타 중 살 수 있는것이 없어야 된다는 조건이 있으므로 DP를 다음과 같이 정의한다.

$dp[i][j][k]=i$ 번째 마가리타 이전까지 봤는데, 안 산 것중 가장 싼게 $j$ 번 인덱스이고(안 산게 없다면 $j=0$), 남은 돈이 $k$ 일 때 마가리타의 조합

아무 마가리타를 사지 않은 경우를 경우의 수에 넣어주지 않아야 함에 유의한다.