반응형 tree1 [백준/C++] 트리의 독립집합 (No. 2213) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때, 아무 생각 없이 하나의 노드를 기준으로 두번 검사하면 되겠다는 생각을 했다. 하지만 예제의 입력을 보자마자 착각했다는 것을 깨닫고 다시 풀었다... 새로 푼 방법은 두가지 경우로 나눠서 계산하는 방법으로 트리를 그리면서 계산하는 방법이다. 먼저 그래프가 트리의 형태이므로 한 정점을 기준으로 트리를 그린다. 이후 현재 노드와 하위 노드들(자식 노드들)의 값을 포함해 만들 수 있는 독립집합의 최대값을 DP라는 배열에 저장한다. DP라는 배열을 그리는 이유는 중복된 계산을 줄이기 위해서다. 어떤 .. 2024. 6. 9. 이전 1 다음 반응형
