2021 - 매출 하락 최소화

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

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

[ 문제풀이 ]

2021 카카오 기출 마지막 문제이다. 트리 dp를 이용해서 푸는 문제인데 결국 혼자 힘으로 해결하지 못하였다.

​BaaarkingDog 님의 유튜브 풀이 영상을 참고하여 해결하였다.

· https://www.youtube.com/watch?v=FX9n1PFv2K4

 

우선 각 정점에 대해서 주어질 수 있는 상황은 현재 v 정점이 참석했는지 안 했는지에 대한 여부이다. 따라서 다음과 같이 dp 테이블을 표현할 수 있다.

1. dp[v][0] : v 정점을 선택했을때의 최소값
2. dp[v][1] : v 정점을 선택하지 않았을때의 최소값

v 정점을 참석시키는 1번 상황은 굉장히 단순하다. v와 v의 자식들은 한 팀에 속하기 때문에 v가 참석했다는 의미는 자식들은 참석을 해도 되고 안 해도 된다는 의미이다.

​즉, 자식들이 참석한 상황과 참석하지 않은 상황 중 최소값을 뽑아주면 된다.

​

하지만 2번 상황은 조금 복잡하다. 나도 1번 상황은 해결하였는데 2번 상황을 결국 해결하지 못하였다.

​2번 상황은 v가 참석하지 않기 때문에 자식들 정점 중 무조건 한 정점은 참석해야 한다. 그렇다면 어떤 자식을 참석해야 할까?

​자식 노드를 nv라고 한다면 dfs는 단말 노드부터 루트 노드로 올라오면서 갱신되기 때문에 dp[nv][0]과 dp[nv][1]에는 현재 최적해가 저장되어 있음이 보장된다.

​즉, dp[nv][0] - dp[nv][1]은 자식 nv를 참석시키는 비용을 의미한다. 따라서 우리는 dp[nv][0] - dp[nv][1]의 최솟값을 찾아주면 된다.

 

​주의해야 할 점은 dp[nv][0] - dp[nv][1]의 값이 음수가 나오는 경우이다.

​dp[nv][0]와 dp[nv][1]은 현재 최적해가 저장되어 있기 때문에 dp[nv][0]은 무조건 dp[nv][1]보다 커야 한다. 왜냐하면 dp[nv][0]은 nv를 참석시킨 비용이 추가된 상황이기 때문이다.

​즉, dp[nv][0] - dp[nv][1]의 값이 음수가 나오는 경우는 dp[nv]의 값에는 자식(nv)을 참석시킨 상황이 없다는 것을 의미한다. 따라서 dp[v][1]은 v를 참석시킨 최솟값 dp[v][0]에서 v를 참석시키는 비용을 빼준 것이 v를 참석시키지 않은 최솟값이 된다.

import java.util.*;

class Solution {
	int N;
	List<Integer>[] edgeList;
	int[][] dp;
	
    public int solution(int[] sales, int[][] links) {
        N = sales.length;
        edgeList = new ArrayList[N + 1];
        
        for (int i = 0; i <= N; ++i) edgeList[i] = new ArrayList<>();
        for (int[] link : links) {
        	edgeList[link[0]].add(link[1]);
        }
        
        dp = new int[N + 1][2];
        /*
         * dp[v][0] : v 정점을 선택했을때의 최소값
         * dp[v][1] : v 정점을 선택하지 않았을때의 최소값
         */
        
        dfs(1, sales);
        
        return Math.min(dp[1][0], dp[1][1]);
    }
    
    public void dfs(int v, int[] sales) {
        dp[v][0] = sales[v - 1]; //v를 참석시킴
        
        //단말 노드면 종료
        if (edgeList[v].isEmpty()) {
            return;
        }
        
        int diff = (int)1e9; //자식을 참석시키는 비용
        
        for (int nv : edgeList[v]) {
            dfs(nv, sales);
            
            //v가 참석한다면 v 팀에 속하는 자식들은 참석해도 되고 안해도 됨
            //그 중 최소값을 가지는 상황을 선택하면 됨
            dp[v][0] += Math.min(dp[nv][0], dp[nv][1]);
            
            //v가 참석하지 않는다면 자식들 중 무조건 한명을 참석시켜야 함
            //현재 dp[nv][0]과 dp[nv][1]은 이미 최적해가 저장되어 있음
            //즉, dp[nv][0]은 dp[nv][1]보다 무조건 커야함, 그래야 dp[nv][0]은 자식을 참석시킨 상황이기 때문
            //따라서 자식을 참석시키는 비용(dp[nv][0] - dp[nv][1])이 가장 작은 놈을 구해주면 됨
            //만약, diff가 음수라면 자식을 참석시킨 정점이 없다는것을 의미
            //즉, dp[v][1]은 v를 참석시킨 최소값에서 v를 참석시키는 비용을 빼주는 것이 최소값임 
            diff = Math.min(diff, dp[nv][0] - dp[nv][1]);    
        }
        
        //diff가 음수라면 자식들 중 참석시킨 애가 없기 때문에 dp[v][0]에서 v의 값을 빼줌
        if (diff < 0) {
            dp[v][1] = dp[v][0] - sales[v - 1];
        } 
        //그렇지 않다면 현재 dp[v][0]에서 v가 참석하는 값을 빼주고 diff를 더해주면 됨
        //diff를 더해주는 이유는 현재 dp[v][0]에는 dp[nv][0], dp[nv][1] 중 최소값이 들어있기 때문에
        //자식(nv)을 참석시키는 비용 diff만 더해주면 됨
        else {
            dp[v][1] = dp[v][0] - sales[v - 1] + diff;
        }
    }
}