백준 2213 트리의 독립집합
-
[JAVA] 백준 2213 트리의 독립집합알고리즘 공부/문제 풀이 2021. 11. 9. 21:32
https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net - 어려웠다.. 결국 블로그의 도움을 받아 해결하였다 - 트리의 구조 -> 어느 정점이든 루트가 될 수 있다 -> 편의상 1번 정점을 루트로 생각하고 1번 노드부터 dfs 탐색을 진행한다 - 현재 접근한 노드를 포함할 때/포함하지 않을 때의 최대 독립 집합의 가중치를 구해본다 => memo[N][2] - 현재 노드를 집합에 포함한다면, 인접한 다음 노드는 포함되지 ..