DP를 재귀로 풀기에 난해한 문제들이 있다. [할로윈의 양아치 (https://www.acmicpc.net/problem/20303)](https://fly-ram.notion.site/https-www-acmicpc-net-problem-20303-128817f254f980959bfcebb9321bc139) 문제처럼 최종적인 답을 구하기 위해 가장 작은 답부터 만들어가는 bottom-up으로 풀이하는 게 자연스러울 때가 있다.
이 문제도 genre별 권수에 따른 최대값이 이미 정해져 있어서 k번째 판매 권수와 g번째 장르에 따른 점화식으로 풀이가 가능했다.
ex) ~ K까지의 무게를 채우며 최대 비용을 구하시오. N권 중 K권을 팔면서 얻을 수 있는 최대값을 구하시오.
포인트는 N개의 요소가 서로 독립적이어서 순서가 없는 것이더래도 배열에서 주우욱 훑으며 최댓값을 계산해나가도 된다는 것이다.
우선순위 큐로 그리디하게 풀 수 있는 걸까.. 한참 고민하다가, 답의 경우가 여러 가지가 존재할 수 있음을 깨닫고 DP를 통해 bottom-up 방식으로 ‘답에 팀장이 포함될 때와 아닐 때’의 해를 구해 나가면 최소 해를 얻을 수 있음을 눈치챘다!
서브트리에 대해 루트를 포함할 때와 아닐 때의 해를 구분하는 게 필요하다면 트리 DP를 사용하기 좋은 상황이다.
나는 위상정렬 + queue를 이용해서 풀이했으나, 다른 사람들 소스 코드 중 DFS 형태로 leaf일 때 종료하는 방식을 많이 사용했다. 좋은 방법이다. 트리 DP를 만나게 되면 DFS의 종료 조건을 이용하는 방식으로 코드를 짜보아야겠다.
기본은 파라메트릭 서치로 답을 구하는 것.
N * N 만큼의 cache 메모리가 필요한 게 아닌가 고민N * 3 만큼의 cache 메모리 사용N 만큼의 cache 메모리가 있으면 됨을 이해pair<int, int> 타입을 사용.