-
카드 팩은 다양하다 → 각 카드 팩은 다양한 개수의 카드가 포함되어 있다
-
카드 팩에 담긴 카드 개수가 적고 비싸면, 좋은 카드팩 아닌가?? 라고 생각한다고 함
-
카드 N 개를 사기 위해 “가장 큰 비용” 이 드는 경우를 찾고 싶다
-
개수를 딱 맞춰야 한다.
-
카드팩을 “중복해서 선택” 하는 것이 가능하다.
-
cnt 와 cost 라고 생각한다면
-
cnt 개가 남아 있는 경우
- 선택지 들 은 cnt 이하 개의 카드가 포함된 팩 들을 선택 할 수 있다
-
cnt 개가 남아 있을 때, 앞으로의 선택에 따라 여러 경우가 나오긴 하지만,
- 결국은 cnt 개가 남게 되면, 그 때부터 해당 subproblem 들은 동일한 서브 프로블럼이 된다
1,2,3,4,5 팩이 존재하고 4개를 선택해야 하는 경우
1선택 : 3개 남음 → 1 선택 : 2개 남음 → 1 선택 : 1개 남음 → 1선택
1선택: 3개 남음 → 2 선택 → 1개 남음 → 1선택
1선택: 3개 남음 → 3선택
2 선택: 2개 남음 → 1선택 : 1개 남음 → 1선택
3 선택: …….
대충 이렇게만 봐도, “ 2개 남음 → 1선택 : 1개 남음 → 1선택” 이런 부분이 중복됨을 확인 할 수 있음
코드 -> 깃허브
