(백준) 신년 파티 _ 1623

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

 

🐢 설명

트리DP + 트래킹 문제이다.

 

문제를 정리해보면 자신의 직속상사가 참가하면 자신은 참가하지 않고, 직속상사가 불참하면 자신은 참가할 수 있으며 && 참가자들의 날나리 정도의 합이 최대가 되도록 하는 멤버 및 그때의 날나리 합을 구하면 된다. 근데 이때 사장이 참여하는 경우 / 참여하지 않는 경우 2가지에 대해 구해야 한다.

 

먼저, 상사의 참가여부에 부하의 참가여부가 달라지는 경우는 일반적인 트리 DP 문제로 2차원 dp배열을 통해 풀 수 있다.

• 상사가 참여하는 경우
  • 부하는 참여하지 못함
• 상사가 참여하지 않는 경우
  • 부하는 참여하거나
  • 부하는 참여하지 않음

이렇게 케이스를 나눠서 dp를 채워주면 된다.

 

하지만 이 문제에서는 추가적으로 참여하는 멤버를 뽑아줘야 하므로 추적을 위해 check[]을 추가로 필요로 한다. dp배열을 채울 때

참가일 경우 check[true]로 하고, 참가하지 않을 경우 check[false]를 해주면 된다.

 

이후 dfs로 탐색이 종료되고 난 후 사장 참여하는 경우 / 안하는 경우 나눠서 trace리스트를 check배열을 확인하면서 채워준다. 이때 상관이 참여하지 않는다고 해서 부하가 바로 참여하는게 아니라, check배열에서 더 이득이 되는 경우를 따져서 체크해주었으므로 trace를 채울 때도 상관이 불참일 때 부하의 참여여부를 보고 넣어줘야 한다. 

 

🐢코드

public class Main {
	static int N;
	static int[][] dp;
	static int YES = 0;
	static int NO = 1;
	static ArrayList<Integer> adj[];
	static ArrayList<Integer> trace;
	static boolean[] check;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		dp = new int[2][N + 1];
		adj = new ArrayList[N + 1];
		check = new boolean[N + 1];

		st = new StringTokenizer(br.readLine());
		for (int i = 1; i < N + 1; i++) {
			adj[i] = new ArrayList<>();
			dp[YES][i] = Integer.parseInt(st.nextToken());
		}

		st = new StringTokenizer(br.readLine());
		for (int i = 2; i < N + 1; i++) {
			int boss = Integer.parseInt(st.nextToken());
			adj[boss].add(i);
		}

		StringBuilder answer = new StringBuilder();
		trace = new ArrayList<>();

		dfs(1);
		answer.append(dp[YES][1]).append(" ").append(dp[NO][1]).append("\n");

		// 사장이 참여할 때 참가자 추적
		traceDfs(1, YES);
		trace.sort(null);
		for (Integer t : trace) {
			answer.append(t).append(" ");
		}
		answer.append("-1").append("\n");

		// 사장이 불참할 때 참가자 추적
		trace.clear();
		traceDfs(1, NO);
		trace.sort(null);
		for (Integer t : trace) {
			answer.append(t).append(" ");
		}
		answer.append("-1");

		System.out.println(answer);
	}

	private static void dfs(int root) {
    	// 일단 상사는 참여한다고 체크
		for (Integer child : adj[root]) {
			dfs(child);
			dp[YES][root] += dp[NO][child];
			check[root] = true;

			// 부하가 참여하는거가 이득이면 부하가 참여한다고 체크
			if (dp[YES][child] >= dp[NO][child]) {
				check[child] = true;
				dp[NO][root] += dp[YES][child];
			} else {
			// 부하가 불참하는거가 이득이면 부하가 불참한다고 체크
				check[child] = false;
				dp[NO][root] += dp[NO][child];
			}
		}
	}

	private static void traceDfs(int root, int isCome) {
		if (isCome == YES) {
			trace.add(root);
		}

		for (Integer child : adj[root]) {
        	// 상사가 참여면 부하는 무조건 불참
			if (isCome == YES) {
				traceDfs(child, NO);
			} else {
            	// 상사가 불참이면 부하는 참여여부를 보고 참여
				if (check[child]) traceDfs(child, YES);
				else traceDfs(child, NO);
			}
		}
	}
}

🐢 마무리