[백준/BOJ] 백준 2213번 : 트리의 독립집합

www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 �� www.acmicpc.net 트리에서 다이나믹 프로그래밍(트리DP?)를 이용해 문제를 해결했다. 해당 노드를 독립 집합에 포함하는지, 포함하지 않는지에 따라 해당 노드를 루트로 하는 트리의 최대 독립 집합의 크기를 구하는 방식으로 트리의 최대 독립 집합의 크기를 구한다. 최대 독립 집합에 속하는 정점을 구하는 방법은, 이전 노드가 최대 독립 집합에 선택되었는지를 판단하여 이전 노드가 최대 독립 집합에 ..

2020.10.04