(C++) - 백준(BOJ) 17831 : 대기업 승범이네

https://www.acmicpc.net/problem/17831

17831번: 대기업 승범이네

tree dp 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

 사수, 부사수 관계를 인접 그래프로 나타내기 위한 변수 graph, 각 회사원의 능력을 입력할 일차원 배열 ability, 회사원의 수 n, dp함수를 수행하며 memoization을 수행할 d배열을 선언 후 입력받습니다. graph에 값을 저장할 때 i번 회사원의 사수를 입력하는 형태이므로 graph[사수]의 자식 i형태로 push_back해줍니다.

 

📔 풀이과정

 멘토링을 하는 방식에는 다음과 같은 규칙이 있습니다. 다음 규칙에 따라 treeDp함수를 top down방식으로 수행합니다.

 

 1. num이라는 사원이 멘토를 가지고 있는 경우(stat이 0인 경우)  num의 부사수들은 모두 num을 멘토로 가질 수 없습니다. num의 부사수들을 next라고 하면   d[num번 사원][멘토 있음] += for 모든 부사수들, d[num의 부사수번호][멘토 없음]을 공식으로 가지게 됩니다.

 

 2. num이라는 사원이 멘토를 가지고 있지 않은 경우(stat이 1인 경우)  이 경우에는 부사수들은 두 가지의 방식을 취할 수 있습니다.

 

  2-1. num과 멘토링을 모두 하지 않는 경우

  num과 멘토를 하지않은 menti들의 시너지 합을 구할 변수 mentiNot을 선언 후 0으로 초기화해줍니다.

  mentiNot += for 모든 부사수들, d[num의 부사수번호][멘토 없음] 라는 공식이 성립하게 됩니다.

  이후 max(d[num사원][멘토여부], mentiNot)를 저장해줍니다.

 

  2-2. num의 부사수들 중 한 명이 num과 멘토링할 경우

  미리 구해놓은 mentiNot 변수의 값을 활용해야 합니다. 그렇지 않으면 모든 부사수에 대해 멘토링을 할 부사수를 정하고, 나머지 인원들을 멘토를 가지지 않았을 때의 최댓값을 구하는 방식을 반복하기 때문에 시간초과가 나게 됩니다. 먼저 next부사수와 멘토링을 할 때마다 시너지 최댓값을 저장하기 위해 변수 menti를 선언 후 0으로 초기화해줍니다.

  매번 멘토, 멘티를 정해 짝지을 때마다 다음과 같은 공식이 적용됩니다.  menti = mentiNot - next와 num사원이 멘토링을 하므로 기존에 멘토링을 하지 않기로 했을 때의 최댓값 + next와 num사원이 멘토링을 할 때 최댓값 + next와 num의 시너지

  이후 max(d[num사원][멘토여부], menti)를 저장해줍니다.

  

📔 정답출력

treeDp의 반환값을 출력해줍니다.

---

📕 Code

Top Down

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll ability[200001], d[200001][2], n;
vector <ll> graph[200001];
ll treeDp(ll num, ll stat){
    ll &ret = d[num][stat];
    if(ret != -1) return ret;
    ret = 0;

    //num사원이 멘토를 가지고 있다면 num의 부사수들은 num과 멘토링 못함
    if(stat) {
        for(auto next : graph[num]) ret += treeDp(next,0);
    }

    //num사원이 멘토를 가지고 있지 않다면 num의 부사수 중 한명이 num과 멘토링하거나 아예 안할 수 있음
    else {
        ll mentiNot = 0, menti = 0;
        for(auto next : graph[num]) mentiNot += treeDp(next, 0);
        ret = max(ret, mentiNot);
        for(auto next : graph[num]){
            ll synergy = ability[next] * ability[num];
            menti = mentiNot - treeDp(next,0) + treeDp(next, 1) + synergy;
            ret = max(ret, menti);
        }
    }
    return ret;
}

int main(){
    memset(d, -1, sizeof(d));
    cin >> n;
    for(int i = 2, x; i <= n; i++) {
        cin >> x;
        graph[x].push_back(i);
    }
    
    for(int i = 1; i <= n; i++) cin >> ability[i];
    cout << treeDp(1, 0);
}