[BOJ] 백준 [17831] 대기업 승범이네 JAVA

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

17831번: 대기업 승범이네

[문제]

[풀이]

굉장히 어려웠다 .. 뚝배기 갈리는 문제다.

우선 , 특정 i번째 노드 입장에서 생각해보자.
i 입장에서는 2가지 경우가 있다.
1. i 노드와 i 의 자식들간에 시너지를 맺을 때.
2. i 노드가 이미 부모노드와 시너지가 맺혀 있을때.

그렇기 때문에 특정 i 번노드 입장에서는 시너지로 묶여있는지 아닌지에 대한 여부에 따라서
i 번 까지의 시너지 총 합이 달라진다. 즉 , 변수는 ( 특정노드 , 묶여있는지 아닌지) 이기 때문에
점화식을 세울 때 dp[노드의갯수][묶여있는지 여부] 로 나타 낼 수 있다.

다시 돌아와서 , 만약 i번 노드가 부모노드랑 관계가 맺혀있지 않다면 ( 1번의 경우 )
또 두 가지의 선택이 있다. 
a. 자식간에 시너지를 맺을지
b. 자식간에 시너지를 맺지 않을지

a 의 경우든 b 의 경우든 간에 분명한 것은 i 번 노드의 시너지 총합은 i의 자식을 next로 했을 때,
우선은 dp[i][?] += dp[next][0] 이라는 것.
b 인 경우는 그냥 i 의 자식개수 만큼 순회를 돌면서 합해주면 된다.
a 인 경우는 특정 자식을 next 라고 했을 때
dp[i][?] = (b의 경우에서 구한 시너지합)+dp[next][1] - dp[next][0] + i의가중치*next의가중치 가 된다.
next와 시너지를 맺기 때문에 dp[next][1]을 더해주고 , 기존에 합에서 dp[next][0]을 빼는것.

이렇게 DFS를 통해 반복하다 보면 시너지의 총합이 dp[1][0] 쪽에 다 채워지게 된다. 

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main {
    static ArrayList<Integer>[] list;
    static int[][] dp;
    static int[] weight;
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        list = new ArrayList[n+1];
        weight = new int[n+1];
        dp = new int[n+1][2];
        for(int i=1;i<=n;i++) list[i] = new ArrayList<>();
        int[] input = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        for(int i=0;i<input.length;i++) list[input[i]].add(i+2);
        input = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        for(int i=1;i<=n;i++) {
            Arrays.fill(dp[i],-1);
            weight[i]=input[i-1];
        }
 
        System.out.println(dfs(1,0));
    }
 
    private static int dfs(int cur,int isBind) {
 
        if(dp[cur][isBind] != -1) return dp[cur][isBind];
 
        dp[cur][isBind]=0;
        for (Integer next : list[cur]) dp[cur][isBind] +=dfs(next,0);
 
        if(isBind==0){
            int sum = dp[cur][isBind];
            for (Integer next : list[cur])
                dp[cur][isBind] = Math.max(dp[cur][isBind],
                        sum-dfs(next,0)+dfs(next,1)+weight[cur]*weight[next]);
        }
 
        return dp[cur][isBind];
    }
 
}