이 문제처럼 "x번째 물건을 K_x개까지 가져갈 수 있다"는 조건이 붙는 배낭 문제는 x번째 물건을 K_x개 복사한 뒤 "모든 물건은 하나씩만 가져갈 수 있다"는 조건이 붙는 배낭 문제로 바꿀 수 있고, 이것이 질문에 올리신 풀이와 비슷합니다. 문제는 이렇게 하면 물건이 너무 많아진다는 것입니다.
예를 들어, K=3인 물건 X가 있어서 이것을 3개 복사했다고 해 봅시다. 각각의 복사에 A, B, C라고 이름붙이면, A, B를 가져가는 거나, B, C를 가져가는 거나, A, C를 가져가는 거나 아무 차이가 없습니다. 셋 다 "물건 X를 두 개 가져간다"와 동일한 의미를 갖는 것입니다. 그런데 이렇게 복사해 놓고 DP를 하면 세 경우 모두를 고려하고 똑같은 DP값을 여러번 계산하게 됩니다. 물건 X을 가져가는 경우의 수는 원래 0부터 3까지 총 4가지였는데, 이렇게 복사하면 23=8가지가 되므로 상당량의 중복이 생깁니다.
하나 발상의 전환을 하면 물건을 3개보다 적게 만들고도 물건 X를 가져가는 4가지 경우의 수를 모두 표현할 수 있습니다.
qls0860 5년 전
도대체 어떤 점화식을 짜야 시간 초과가 안날까요...
배열 다 그리면서 점화식 짜봤는데 시간 초과가 나요
너무 어렵습니다 ㅠㅠ