본문 바로가기

Problem Solving/Baekjoon Online Judge (Gold)

백준 1623 - 신년 파티 (C++)

문제

  • 문제 링크
  •   
       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[p][0] = Σmax(dp[i_k][0], dp[i_k][1])$
  • $dp[p][1] = ΣN_p + dp[i_k][0]$

  • 가 되겠다.

    경로 추적은 $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(11<< ' ' << f(10<< '\n';
     
        g(11);
        sort(an.begin(), an.end());
        an.push_back(-1);
     
        for (int& i : an) cout << i << ' ';
        an.clear();  cout << '\n';
     
        g(10);
        sort(an.begin(), an.end());
        an.push_back(-1);
     
        for (int& i : an) cout << i << ' ';
    }
    int main()
    {
        Init();
        Solve();
    }
    cs


    comment