Thursday, January 16, 2014

acmicpc.net 2187 - 분해반응

문제 링크(acmicpc.net 2197)

한 개의 트리(정점 n개, 간선 n-1개)에서 m개의 정점만을 남기기 위한 최소 간선 삭제 횟수를 구하는 문제로서 전형적인 tree dynamic programming 문제이다.

d[i][j] : i번 노드의 위치에서 j개의 정점을 없앨 때의 최소 필요 분해 횟수

d[x][n-m]의 유효한 값 중 최솟값 답이 된다.

주의해야할 점으로 i번 노드의 위치에서 k번째 자식을 볼 때, k번째로 인한 테이블 갱신을 먼저 한 후에, k번째가 가지고 있던 값 중 더 좋은 값을 i번째가 취해야한다. 그렇지 않으면 같은 부트리에서 중복되는 결과를 가져오기 때문이다.

No comments:

Post a Comment