BOJ - 대기업 승범이네 17831번 (JAVA, Python)

❓ 문제 - 백준 대기업 승범이네 17831번 - JAVA, Python 풀이법

 

출처 

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

17831번: 대기업 승범이네

 

 

 

📝 문제해결법

1. 이 문제는 DFS + DP == Tree DP로 해결했다.

• 2차원 리스트를 통해 i인덱스를 멘토로하는 멘티의 값을 리스트에 넣어준다.
• dp[i][0]은 i번째 사람이 멘티거나 아무것도 아닐 때의 시너지의 합의 최대값이며, dp[i][1]은 i번째 사람이 멘토일 때 시너지의 합에 최대값을 저장한다.
• dfs를 통해 1번 즉, 승범이가 0(멘티이거나 아무것도 아닐 때) or 승범이가 1 (멘토일 때) 인 루트노드부터 DFS를 타고 내려가면서 시너지 합의 최대값을 구하면 된다.
• 만약 현재 노드가 멘티이거나 아무것도 아닐 때는 밑에 연결된 애들이 어떤 거이든 상관없으므로 연결된 노드의 최대값 들을 더해줘서 해당 dp에 저장한다.
• 현재 노드가 멘토일 경우가 중요한데 현재 노드가 멘토이면 연결된 노드 중 하나는 무조건 멘티가 있어야 한다. 일단 연결된 노드가 어떤 경우이든 최대 시너지합들을 더해주고, 그 때의 연결된 노드의 상태(멘티or 멘토 이거나 멘토)를 checked 배열에 저장한다.
• 다시 연결된 노드를 꺼내서 현재 노드와 연결된 노드가 멘티-멘토 관계가 1개이고, 나머지는 시너지합이 최대인 경우로 유지하도록 계속 시너지합의 최대값을 찾고 DP에 저장한다.

2. 느낀점

• Tree DP인 것은 예상이 갔으나.. 멘토, 멘티일 때 를 어떻게 나눠서 처리해야하는지 감이 오지 않았다. 그래서 다른 사람들 풀이를 참고해서 가장 이해하기 쉬운 것을 공부하고 파이썬 코드와 자바코드로 변경했다. Tree DP 쉽지 않은 녀석이지만 ^^ 많이 풀다보면 익숙해지고 잘 풀 수 있을 거다. 아자아자!

 

 

💻 소스코드 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main_17831 {
	public static int n;
	public static int[] power;
	public static int[][] dp;
	public static int ans;
	public static int[] checked;
	public static ArrayList<ArrayList<Integer>> connect;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		power = new int[n+1];
		dp = new int[n+1][2];
		checked = new int[n+1];
		connect = new ArrayList<ArrayList<Integer>>();
		connect.add(new ArrayList<>());
		connect.add(new ArrayList<>());
		for(int i=0;i<=n;i++) {
			connect.add(new ArrayList<>());
		}
		for(int i=2;i<=n;i++) {
			int num = Integer.parseInt(st.nextToken());
			connect.get(num).add(i);
		}
	
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=1;i<=n;i++) {
			power[i] = Integer.parseInt(st.nextToken()); 
			dp[i] = new int[] {-1, -1};

		}

		ans = 0;
		ans = Math.max(dfs(1,0), dfs(1,1));
		
		System.out.println(ans);
	}
	
	public static int dfs(int x, int stat) {
		int max_sum = dp[x][stat];
	
		if(max_sum != -1) {
			return max_sum;
		}
		max_sum = 0;
	
		// 현재 노드가 멘티 or 아무것도 x
		if(stat == 0) {
			int sum = 0;
			for(int i:connect.get(x)) {
				sum += Math.max(dfs(i, 0), dfs(i, 1));
			}
			max_sum = Math.max(max_sum, sum);
		} else {
			// 현재 노드가 멘토 경우 -> 연결된 노드 중 하나의 멘티가 존재해야함
			int temp = 0;
			for(int i:connect.get(x)) {
				int temp1 = dfs(i, 0);
				int temp2 = dfs(i, 1);
				if(temp1 > temp2) {
					temp += temp1;
					checked[i] = 0;
				} else {
					temp += temp2;
					checked[i] = 1;
				}
			}
			
			for(int i:connect.get(x)) {
				int sum = temp - dfs(i, checked[i]);
				sum += (dfs(i, 0) + power[i]*power[x]);
				max_sum = Math.max(max_sum, sum);
			}
			
			
			
		}
		dp[x][stat] = max_sum;
		
		return max_sum;
	}

}

💻 소스코드 (Python)

# BOJ - 대기업 승범이네(17891번)
# Tree DP
import sys
sys.setrecursionlimit(400000)

input = sys.stdin.readline

n = int(input())

graph = [[] for i in range(n+1)]
select = [0 for i in range(n+1)]
lst = list(map(int, input().split()))

for i in range(len(lst)):
    graph[lst[i]].append(i + 2)


power = [0] + list(map(int, input().split()))
visited = [False for _ in range(n+1)]
dp = [[-1, -1] for _ in range(n+1)]

def dfs(x, stat):
    max_sum = dp[x][stat]
    if max_sum != -1:
        return max_sum
    max_sum = 0

    # 현재 노드가 멘티 or 아무 것도 x
    if stat == 0:
        sum = 0
        for i in graph[x]:
            sum += max(dfs(i, 0), dfs(i, 1))
        max_sum = max(max_sum, sum)
    else: # 현재 멘토인 경우
        sum = 0
        for i in graph[x]:
            temp1 = dfs(i, 0)
            temp2 = dfs(i, 1)
            if(temp1 > temp2):
                sum += temp1
                select[i] = 0
            else:
                sum += temp2
                select[i] = 1
        for i in graph[x]:
            sum2 = sum - dfs(i, select[i])
            sum2 += (dfs(i, 0) + power[i] * power[x])
            max_sum = max(max_sum, sum2)
    dp[x][stat] = max_sum
    return max_sum



ans = max(dfs(1, 0), dfs(1, 1))


print(ans)