깨달은 점: 무게가 K 이하~ 와 같이 제한이 있는 상태에서 최댓값을 구하려면 [][K]의 k를 1부터 점차 증가시켜가며 이를 만족하는 아이템을 앞에서부터 채워 온다는 컨셉으로 가야 한다.
분리 집합으로 아이의 수와 사탕을 무게와 비용의 배낭 문제로 변경 가능하다.
배낭을 풀이하기에 크기가 [30000][3000]이 되는데.. [전체 아이의 수][K의 최대값] 이 되기 때문이다.
풀이 가능했던 핵심 아이디어는 아래와 같다.
‘현재 i번째 아이가 답에 포함된다면, cache[i][k] = cache[i - 1][k - i번째 아이의 무게]’
위를 점차 증가시켜가며 만들기 위해 k를 1일 때부터 증가시켜가며 답을 구해두면 DP로 풀이 가능하다.
매번 새로 구하면 절대 안될 것 같은 느낌이 왔다. DP가 필요하다.
깨달은 점: $cache[n] += cache[n - p]$ 형태로 수를 차례대로 쭉쭉 더해가면 조합 문제를 푸는 것처럼 해집합을 구성할 수 있다. $n$을 만들 때 이미 $n - p$까지 구성했다면 뒤에 $p$를 넣는 방식이다.
하나의 기업을 보고, 이 결과와 함께 다음 기업을 보면 다음 기업의 탐색 결과 안에는 이전 기업까지 고려한 결과가 누적된다. 같은 방식으로 다음다음 기업, 다음다음다음 기업, … 마지막 기업을 탐색할 때 마지막 이전의 결과에 그때까지의 모든 결과가 누적돼 있어서 마지막 기업을 고려한 최종 결과만으로 답을 구할 수 있다.
역추적 과정은 거꾸로 최종 결과로부터 하나씩 풀어오는 과정으로 답을 도출할 수 있다.