트리의 독립집합 (1) 썸네일형 리스트형 [BOJ] 백준 2213 트리의 독립집합 (Swift) 문제 https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 풀이 트리에서 DP를 사용하는 문제입니다. 독립 집합을 만들 때, 최대 가중치를 구하기 위해 다음과 같이 작성할 수 있습니다. 현재 노드를 선택헀다면, 다음 노드를 선택 못함 (현재노드의 가중치를 더함) 현재 노드를 선택하지 않았다면, 다음 노드를 선택하거나 안하거나. max(다음 노드를 선택한 값, 다음 노드 선택 안한 값) 점화식은 다음과 같이 세울 수 있.. 이전 1 다음
