2021 KAKAO BLIND RECRUITMENT - 매출 하락 최소화 (JAVA)

❓ 문제 - 2021 KAKAO BLIND RECRUITMENT 매출 하락 최소화 - JAVA 풀이법

출처 

(https://programmers.co.kr/learn/courses/30/lessons/72416)

코딩테스트 연습 - 매출 하락 최소화

 

 

📝 문제해결법 

1. Tree DP로 해결해야한다.

 

우선, Tree DP 에서 Top-down 방식으로 루트 노드부터 dp에 최소화된 매출액의 합 생각했는데..

다른 노드로 갈 수록 고려해야할 사항이 많아져서.. 식을 유도하지 못 했다.

 

카카오 풀이를 먼저 찾아봤는데 

 

최적의 해는 DFS로 방문한 순서의 역방향으로 차례대로 결정이 되며, 리프 노드에 대한 최적해가 처음에 정해지고, 마지막에야 비로소 1번 루트 노드에 대한 최적해를 구할 수 있습니다.

 

d[i][0] : i번 노드가 루트인 서브트리에서, i번 노드가 워크숍에 불참하는 경우의 최적해

d[i][1] : i번 노드가 루트인 서브트리에서, i번 노드가 워크숍에 참석하는 경우의 최적해

 

라고 bottom-up 방식을 통해서 접근해야 최적해를 dp에 저장할 수 있다.

 

(https://loosie.tistory.com/188) 분의 풀이를 참고해서 코드를 작성했다.

 

중요한 흐름은 연결된 자식 노드가 있는 서브트리까지 dfs를 타고 들어간 다음에

서브 트리 내 루트를 기준으로 자기 자신을 참석시킬 때의 최적해와

자기 자신을 참석시키지 않을 떄의 최적해를 dp에 저장한다.

 

이때, 경우의 수를 나눠서 따져야 하는데

 

1) 서브트리의 루트노드가 참석할 경우, 서브트리의 자식 노드가 참석하지 않을 경우

2) 서브트리의 루트노드가 참석할 경우, 서브트리의 자식 노드가 참석할 경우

3) 서브트리의 루트노드가 참석하지 않을 경우, 서브트리의 자식 노드가 참석할 경우

 

이런 경우만을 고려해서 최소화된 매출액의 합을 구해야 한다.

 

if(dp[child][0] < dp[child][1]) {
				dp[idx][0] += dp[child][0];
				dp[idx][1] += dp[child][0];
				
				extra = Math.min(extra, dp[child][1] - dp[child][0]);
		} else {
				
				dp[idx][0] += dp[child][1];
				dp[idx][1] += dp[child][1];
				
				extra = 0;
	}

 

이 부분이 위 경우를 고려한 코드인데,

 

만약 연결된 자식 노드가 포함되지 않았을 때가 최적해를 가진다면

해당 경우를 현재 서브 트리의 루트 노드에 더해준다.

 

만약 dp[idx][0] ->

즉 서브 트리의 루트노드도 참석하지 않고, 자식 노드 모두 다 참석하지 않으면

주어진 조건에서 벗어난다. 

따라서 루트노드가 참석하지 않을 때는 자식 노드들 중에서 한 자식 노드라도 참석해야하므로

자식 노드들 중에서 참석했을 때 가장 최적해를 가지는 경우를 extra에 최솟값 갱신을 통해 구한 뒤  

extra를 dp[idx][0]에 더해준다.

 

 

또한 extra에 왜 dp[child][0]을 빼주는가 했을 때 앞에서 이미 dp[idx][0]에 dp[child][0]을 더해줬기 때문이다.

 

 

2. 느낀점

 

막상 풀이를 찾고 해결해보니

(https://developer-ellen.tistory.com/152) 의 백준에 대기업 승범이네라는 문제랑 유사했다!

Tree DP 문제를 더 많이 풀어봐서 

여러 조건일 때도 코드를 구현할 수 있게 실력을 키워야겠다.

 

 

💻 소스코드 

import java.util.ArrayList;

public class Solution {
	public static ArrayList<ArrayList<Integer>> link;
	public static int[][] dp = new int[300001][2];
	public static void main(String[] args) {
		int a = solution(new int[]{14, 17, 15, 18, 19, 14, 13, 16, 28, 17}, 
				new int[][]{{10, 8}, {1, 9}, {9, 7}, {5, 4}, {1, 5}, {5, 10}, {10, 6}, {1, 3}, {10, 2}}
				);
	
		System.out.println(a);
	}
	
	public static int solution(int[] sales, int[][] links) {
		link = new ArrayList<>();
		
		for(int i=0;i<sales.length+1;i++) {
			link.add(new ArrayList<>());
		}
		
		for(int i=0;i<links.length;i++) {
			int a = links[i][0];
			int b = links[i][1];
			link.get(a).add(b);
		}
		
		dfs(sales, 1);
		int answer = Math.min(dp[1][0], dp[1][1]);
		return answer;
	}
	
	public static void dfs(int[] sales, int idx) {
		dp[idx][0] = 0;
		dp[idx][1] = sales[idx-1];
		
		if(link.get(idx).size() == 0) return;
		int extra = (int)1e9;
		for(int child:link.get(idx)) {
			dfs(sales, child);
			
			if(dp[child][0] < dp[child][1]) {
				dp[idx][0] += dp[child][0];
				dp[idx][1] += dp[child][0];
				
				extra = Math.min(extra, dp[child][1] - dp[child][0]);
			} else {
				
				dp[idx][0] += dp[child][1];
				dp[idx][1] += dp[child][1];
				
				extra = 0;
			}
		}
		
		dp[idx][0] += extra;
		return;
	}

}