트리 DP와 비트마스크 DP 문제 풀이
P1352 상사 없는 파티
트리에서 인접한 노드를 동시에 선택할 수 없는 상황에서 최대 가중치 합을 구하는 문제입니다.
상태 정의: val[node][0/1] - 현재 노드를 포함하지 않는 경우(0) 또는 포함하는 경우(1)의 하위 트리 최대값
점화식:
val[node][1] = weight[node] + Σ val[child][0] (현재 노드를 선택하면 자식들은 선택 불가)
val[node][0] = Σ max(val[child][0], ...
7월 3일 21:12에 게시됨
알고리즘 문제 해결 및 코드 구현
트리의 깊이 우선 탐색 순서 최적화
주어진 트리에서 각 노드는 고유한 가중치를 가지고 있으며, 루트 노드는 1번입니다. DFS 순서에서 짝수 위치에 있는 노드들의 가중치 합을 최대화하는 것이 목표입니다.
문제 해결 방법
이 문제는 트리형태의 동적 프로그래밍(DP)으로 접근할 수 있습니다. 각 서브트리가 제공할 수 있는 최대 점수를 계산하며 진행합니다. 서브트 ...
6월 19일 22:53에 게시됨
NOIP 모의고사 4회 풀이 노트
문제 1: 대회 참가 조합
각 참가자의 대회 참가 여부를 비트마스크로 인코딩하여 [0, 16) 범위의 정수로 표현한다. 이후 각 상태의 비트 개수(popcount)를 기준으로 내림차순 정렬한 뒤, 그리디 전략으로 조합을 구성한다.
핵심 아이디어는 sum[j]가 양수일 때, 현재 상태 j와 겹치지 않는 참가자를 병합하여 새로운 상태를 형성하는 것이다. 초기값을 충분히 큰 값으로 설 ...
5월 25일 10:19에 게시됨