물건이 C개 있다면, 이것을 1개짜리, 2개짜리, 4개짜리, 8개짜리, ... 묶음 판매 상품으로 만들고, 각 상품이 1개씩만 있다고 가정하여 문제를 변형하는 과정입니다.
예를 들어, 어떤 물건이 15개 존재하고 가치가 3이라면, 이를 가치 3, 6, 12, 24를 가지는 상품으로 분할해 각각이 하나씩만 있는 것으로 바꾸어 개수 조건을 없앱니다.
이 경우, 만약 한 개 살 예정이었다면 3짜리를, 두 개 살 예정이었다면 6짜리를, 세 개 살 예정이었다면 3짜리와 6짜리를, ... , 15개 다 살 예정이었다면 3, 6, 12, 24짜리를 모두 구매하는 것과 동치이고, 이러한 구매가 항상 가능함이 보장됩니다. (이진수로 생각해보세요)
이렇게 바꾸고 나면 개수를 무시한 채로(모든 물건이 1개가 되었으므로) 평범한 디피 문제로 바꾸어 풀 수 있습니다.
uiucpass 5년 전 7
코드가 도저히 안풀려서 찾고 찾아서, 문제 푸신분의 코드 제출해보고, 정답자님들의 정답코드를 보니 거의 모두 공통적으로
첨부한 코드가 꼭 다 포함되어있더라구요.. 저게 무슨 과정인지 여쭙고싶습니다.