[BOJ17831] 대기업 승범이네

문제 설명

문제 링크

• 트리 모양으로 판매원들의 사수, 부사수 관계가 주어진다.
• 이때 두 판매원끼리를 멘티, 멘토관계로 만들 수 있다.
• 한명의 판매원은 하나의 관계에만 속할 수 있다.
• 판매원들의 실력이 트리 노드의 값으로 주어진다.
• 멘티, 멘토관계로 판매원들을 묶었을 때, 하나의 멘티 멘토관계의 값은 멘티의 값 * 멘토의 값이 된다.
• 회사의 총 시너지 값은 모든 멘티 멘토의 값의 합으로 주어진다.

풀이 과정

• 트리 DP 문제다.
• 현재 노드가 부모 노드와 멘티,멘토 관계를 맺고 있는지와 아무 관계를 맺고있지 않은지 2가지 경우를 통해 점화식을 세울 수 있었다.
• status는 관계를 맺고 있는지 아닌지를 구분하는 상태를 표시하는 역할을 한다. 1은 부모와 관계를 맺고있을 때, 0은 아무 관계를 맺고있지 않을 때로 나눈다.

Case 1 부모 노드와 관계를 맺고 있을 때

• dp[n][1]은 현재 노드 n이 부모와 관계를 맺고 있을 때다.
• 이때는 간단하다. 현재 노드 n의 자식노드들이 모두 그들의 부모노드, 즉 n과 관계를 맺고 있지 않는다.
• n의 자식 노드들을 nn1, nn2, nn3 .. 라 한다면,
• dp[n][1] = dp[nn1][0] + dp[nn2][0] + …
• case 2 설명을 위해 위의 식의 우항을 sum이라고 별칭을 지어두겠다.

Case 2 부모 노드와 관계를 맺고 있지 않을 때

• 이때도 먼저 Case 1처럼 n의 자식노드들이 모두 그들의 부모노드 n과 관계를 맺지 않는 경우가 있을 것이다.
• 하지만 여기서 추가로, n의 자식노드들이 n과 관계를 맺는 경우를 생각해봐야 한다.

• 위에 필기한 내용을 각각의 경우의 수마다 진행을 할 경우 경우의 수가 너무 많아지게 된다.
• 하나의 레벨에서도 각각의 자식이 부모와 관계를 맺는 경우에 따라 다른 자식들의 값까지 계속 더해줘야 한다.
• 이 부분에서 고민을 좀 많이했지만, 우리가 구해둔 case 2에서 사용하는 case1을 가지고 해결할 수 있었다.
• 가령 nn1이 n과 관계를 맺고 있는 상황이라고 하면,
• dp[nn1][1] + dp[nn2][0] + dp[nn3][0] + … + score[n] * score[nn1] 이 된다.
• 이 식은 case1에서 sum이라고 표현했던 부분을 통해 쉽게 바꿀 수 있다.
• sum - dp[nn1][0] + dp[nn1][1] + score[n] * score[nn1]
• 즉, 자식 노드만큼 확인해야 했던 작업이 case1의 sum을 가지고 상수 시간에 처리할 수 있게 되었다.
• 저 식을 자식노드만큼 반복하여 가장 max 값을 dp[n][0]에 저장한다.
• case1의 sum 식은 case2에서도 존재하는 경우니깐 그 값을 미리 구해서 사용하면 된다.
• 코드를 통해 확인하자.

import java.io.*;
import java.util.*;

public class BOJ17831_대기업승범이네 {
    static int N;
    static List<Integer>[] adj;
    static int[] score;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(input.readLine());
        adj = new List[N + 1];
        score = new int[N + 1];
        dp = new int[N+1][2];
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < 2; j++) {
                dp[i][j] = -1;
            }
        }
        for (int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<>();
        }
        StringTokenizer st = new StringTokenizer(input.readLine());
        for (int i = 2; i <= N; i++) {
            int n = Integer.parseInt(st.nextToken());
            adj[n].add(i);
        }
        st = new StringTokenizer(input.readLine());
        for (int i = 1; i <= N; i++) {
            score[i] = Integer.parseInt(st.nextToken());
        }
        func(1, 0);
        System.out.println(dp[1][0]);

    }

    static int func(int n, int status) {
        if (dp[n][status] != -1) {
            return dp[n][status];
        }
        dp[n][status] = 0;
        if (status == 1) { // case 1
            for (int i = 0; i < adj[n].size(); i++) {
                int nn = adj[n].get(i);
                dp[n][status] += func(nn, 0);
            }
        }else if (status == 0) { // case 2
            int presum = 0; 
            for (int i = 0; i < adj[n].size(); i++) {
                int nn = adj[n].get(i);
                presum += func(nn, 0);
            } // case1의 sum작업
            dp[n][status] = presum;
            for (int i = 0; i < adj[n].size(); i++) {
                int nn = adj[n].get(i);
                dp[n][status] = Math.max(dp[n][status],
                        presum - func(nn, 0) + func(nn, 1) + (score[n] * score[nn]));
            }
        }
        return dp[n][status];
    }
}