문제
- 문제 링크
BOJ 1623 - 신년 파티
사장을 포함한 직원들의 정보가 트리 형태로 주어진다.
사장이 신년 파티에 포함 될 때 / 되지 않을 때 각각 "날라리 분위기"의 최댓값 및 그 과정을 구해보자.
TL : $2$ sec, ML : $128$ MB
$2 ≤ N ≤ 200,000$ $N_i ≤ |10,000|$
알고리즘 분류
- 다이나믹 프로그래밍(dp)
- 트리(trees)
- 트리에서의 다이나믹 프로그래밍(dp_tree)
풀이
BOJ 27501 - RGB트리
BOJ 2213 - 트리의 독립집합
위 두 문제들이랑 별반 다를게 없다.
풀이 흐름 역시 동일하므로 간단하게만 적고 넘어 가겠다.
$dp[p][q]$ : $p$번 사람을 루트로 하는 서브 트리에서, $p$번 사람의 신년 파티 참석 유무가 $q$일 때의 답 .
$N_i ≤ |10,000|$ 이므로, $dp$ 배열의 기저값 세팅에 주의하자.
구체적으로 $p$가 $i_1, i_2, ..., i_k$의 직속 상관일 때,
가 되겠다.
경로 추적은 $dp$ 에 기록된 최댓값 및 정점의 포함 유무에 주의하여 진행해주면 된다.
전체 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include<bits/stdc++.h> #define N 200001 using namespace std; vector <int> Gr[N], an; int n, a[N], dp[N][2]; void Init() { ios_base::sync_with_stdio(0); cin.tie(0); fill(&dp[0][0], &dp[N - 1][2], 1e9); cin >> n; for (int i(1); i <= n; cin >> a[i++]); for (int i(2), j; i <= n; i++) cin >> j, Gr[j].push_back(i); } int f(int p, int q) { int& t(dp[p][q]); if (t == 1e9) { t = q ? a[p] : 0; for (int& i : Gr[p]) t += max(f(i, 0), (q ? -(int)1e9 : f(i, 1))); } return t; } void g(int p, int q) { if (q) an.push_back(p); for (int i : Gr[p]) g(i, q ? 0 : dp[i][1] > dp[i][0]); } void Solve() { cout << f(1, 1) << ' ' << f(1, 0) << '\n'; g(1, 1); sort(an.begin(), an.end()); an.push_back(-1); for (int& i : an) cout << i << ' '; an.clear(); cout << '\n'; g(1, 0); sort(an.begin(), an.end()); an.push_back(-1); for (int& i : an) cout << i << ' '; } int main() { Init(); Solve(); } | cs |
comment
끝
'Problem Solving > Baekjoon Online Judge (Gold)' 카테고리의 다른 글
백준 26159 - 트리와 수열 (C++) (0) | 2023.05.12 |
---|---|
백준 25498 - 핸들 뭘로 하지 (C++) (1) | 2023.05.12 |
백준 26077 - 서커스 나이트 (C++) (0) | 2023.05.09 |
백준 28018 - 시간이 겹칠까? (C++) (0) | 2023.05.07 |
백준 14554 - The Other Way (C++) (0) | 2023.05.06 |