대기업 승범이네( BOJ 17831 )

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

17831번: 대기업 승범이네

 

문제 파악하기

승범이네 회사의 사원들 중 멘토와 멘티를 적절하게 선택해서 최대의 시너지 효과를 구하는 문제입니다. 승범이네 회사 구조는 트리 구조로 되어있으며 사수와 부사수 관계를 가지고 있는 사원을 멘토-멘티로 선정할 수 있습니다. 결국 이 문제는 현재 노드와 자식 노드를 멘토-멘티로 선정할 것인지, 아니면 현재 노드를 제외할지 탐색해야 하는 문제로 바꿀 수 있습니다. 그리고 이런 경우에는 다이나믹 프로그래밍을 사용하면 쉽게 문제를 해결할 수 있습니다.

 

문제 해결하기

문제를 해결하기 위한 배열 DP를 다음과 같이 정의해봅시다.

DP[idx][used] : 현재(idx) 노드가 사용되었는지(0/1) 여부에 따라 가질 수 있는 시너지의 최댓값

 

used는 현재 노드의 사용 여부를 의미합니다. 0인 경우에는 idx를 이전에 사용하지 않았다는 의미로, 자식 노드 중 하나를 선택해서 멘토-멘티로 선정할 수 있음을 의미합니다. 1인 경우에는 이미 부모 노드와 멘토-멘티 관계를 가지고 있다는 의미로, 어떤 자식 노드와도 멘토-멘티를 선정할 수 없음을 의미합니다. 이렇게 used의 값을 설정하면 사실 알고리즘은 이미 나왔습니다. used의 값에 따라 자식 노드와 멘토-멘티를 선정하거나 선정하지 않는 값 중 최댓값을 DP[idx][used]에 저장하면 됩니다! 이렇게 배열의 의미를 명확하게 정의하면 알고리즘 또한 쉽게 유추할 수 있습니다.

 

그렇다면 이제 알고리즘을 만들어봅시다. 우선, used의 값과 상관 없이 현재 노드(idx)를 선택하지 않는 경우는 항상 탐색하게 됩니다. 그렇기에 DP 배열에 자식 노드로 넘어가는 값을 모두 더해 초깃값을 만들어봅시다.

DP[idx][used] = sum( sv(child1, 0), sum(child2, 0), ... ,sum(childN, 0) );

 

현재 노드(idx)의 모든 자식 노드를 선택하지 않았을 때의 값을 모두 더하면, 우리가 원하는 현재 노드(idx)를 선택하지 않았을 때 가질 수 있는 자식 노드 사이의 시너지의 최댓값을 구할 수 있습니다. 그럼 이번에는 현재 노드(idx)를 선택한 경우에 대해 알아봅시다. 단, 현재 노드를 선택할 수 있는 경우는 항상 used의 값이 0인 경우입니다. 현재 노드(idx)를 선택하여 멘토-멘티를 만들었을 때 중요한 점은 선택하지 않은 자식 노드들의 시너지 값 역시 더해주어야 한다는 점입니다. 따라서, 이 경우에는 다음과 같이 수식을 사용하면 우리가 원하는 결괏값을 얻을 수 있습니다.

DP[idx][used] = max( DP[idx][used], (tot-sv(childT, 0)) + sv(childT, 1)+pf[idx]*pf[childT] );

 

tot는 이전에 구한 DP[idx][used]의 값, 즉 모든 자식 노드들의 시너지 값의 합을 의미합니다. 그리고 pf배열은 사원 개개인의 실력을 의미합니다. 위의 수식은 결국 현재 노드(idx)와 자식 노드(childT)를 멘토-멘티로 만들어 시너지(pf[idx]*pf[childT])를 만들었을 때의 최댓값을 저장하는 수식입니다. 이렇게 현재 노드(idx)가 가질 수 있는 모든 경우를 메모이제이션을 활용하여 효과적으로 탐색하면 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#define NMAX 200010
using namespace std;
 
int N, p;
int pf[NMAX];
 
vector< int > tree[NMAX];
int dp[NMAX][2];
 
int sv(int idx, int used) {
    if(dp[idx][used] >= 0) return dp[idx][used];
 
    int tmp, ret=0;
 
    // idx 노드를 사용하지 않는 경우
    for(int child:tree[idx]) ret += sv(child, 0);
 
    // idx 노드를 사용하는 경우
    if(!used) {
        tmp = ret;
        for(int child: tree[idx]) {
            ret = max(ret, (tmp-sv(child, 0)) + sv(child, 1) + pf[idx]*pf[child]);
        }
    }
 
    return dp[idx][used] = ret;
}
 
int main() {
    // 입력
    scanf("%d", &N);
    for(int i=2;i<=N;i++) {
        scanf("%d", &p);
        tree[p].push_back(i);
    }
    for(int i=1;i<=N;i++) scanf("%d", &pf[i]);
 
    // 탐색
    memset(dp, -1, sizeof(dp));
    printf("%d", max(sv(1, 0), sv(1, 1)));
}

후기

트리를 사용하는 다이나믹 프로그래밍 중 기초적인 문제입니다. 다만, 다른 쉬운 문제들과는 사뭇 다르게 모든 자식 노드의 값을 더해주어야 한다는 점만 유의한다면 어렵지 않게 풀 수 있습니다. 트리를 사용한 구조 및 다이나믹 프로그래밍을 연습할 때 추천하고 싶은 문제입니다.