2584번 - 트리분할
dp(chosen, i, k): i번 노드를 루트로 하는 서브트리에서 총 k개의 노드를 선택했을 때의 간선 가중치의 합의 최솟값 (i번 노드는 chosen의 값에 따라 선택하던지, 선택하지 않던지 함)
으로 놓고 풀려고 시도했는데...
한 노드의 자식 노드가 여러 개일 경우 자식들의 dp값으로부터 부모의 dp값을 구하려면 계산을 너무 많이 해야되네요
어떻게 접근해야 하죠?
답 역추적이... 헠헠... 어렵다...
헉헉 저도 여기서 막힘
댓글을 작성하려면 로그인해야 합니다.
amok 8년 전
dp(chosen, i, k): i번 노드를 루트로 하는 서브트리에서 총 k개의 노드를 선택했을 때의 간선 가중치의 합의 최솟값 (i번 노드는 chosen의 값에 따라 선택하던지, 선택하지 않던지 함)
으로 놓고 풀려고 시도했는데...
한 노드의 자식 노드가 여러 개일 경우 자식들의 dp값으로부터 부모의 dp값을 구하려면 계산을 너무 많이 해야되네요
어떻게 접근해야 하죠?