[프로그래머스] 매출 하락 최소화

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

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

 

DFS 와 동적 계획법을 이용하여 풀 수 있을 거라고는 생각했는데 dp 배열을 구현하기가 어려워서 다른 블로그를 참고하여 풀어나갔다.

 

dp[i][0] : i 가 참석하지 않았을 때의 최솟값, dp[i][1] : i 가 참석했을 때 최솟값으로 정의하고,

기본값으로 dp[i][1] = sales[i-1], dp[i][0] = 0 으로 시작한다.

 

리프 노드부터 후위로 순회하여 각 팀의 팀장의 dp[][] 를 채워나가면서 마지막에 도달하는 dp[1][0] 과 dp[1][1] 을 채워 그 중 최솟값을 구하는 것으로 이해하면 되겠다.

 

map.containsKey(leader) == true 이면 list = map.get(leader) 는 leader 를 팀장으로 하는 팀원들이다.

각 팀원이 참석할 때와 참석하지 않을 때를 비교하여 아래 4가지 상황을 만들 수 있다.

 

1) 팀장이 불참, 팀원이 불참

2) 팀장이 참석, 팀원이 불참

3) 팀장이 불참, 팀원이 참석

4) 팀장이 참석, 팀원이 참석

 

1), 2) 는 팀원이 불참할 때 최솟값을 가지는 경우이며 3), 4) 는 참석할 때 최솟값을 가지는 경우이다.

또한, 1) 의 경우 각 팀에서 한 명 이상이 참석해야 한다는 조건을 만족하기 위해 temp 라는 변수를 만들어 다른 팀원이 참석할 경우의 최솟값을 temp 에 담는다. 

temp = Math.min(temp, dp[팀원][1] - dp[팀원][0]) 이미 dp[leader][0] += dp[팀원][0] 이 되었기 때문에 temp 에는 dp[팀원][1] - dp[팀원][0] 을 담는다. 3), 4) 의 경우, 앞의 조건을 만족하는 경우이므로 temp 를 0 으로 한다.

 

결과적으로, CEO인 1번의 dp 가 채워지면 dp[1][0], dp[1][1](= 1번이 참석하지 않을 때, 참석할 때) 중 최솟값을 반환해준다. 

 

import java.util.*;

class Solution {
    
    public static void rf(int leader, HashMap<Integer, List<Integer>> map, int[] sales, int[][] dp) {
        dp[leader][1] = sales[leader-1];
        int temp = 10000;
        
        if (map.containsKey(leader)) {
            List<Integer> list = map.get(leader);
            
            for (int i : list) {   
                rf(i, map, sales, dp);
                
                if (dp[i][0] < dp[i][1]) {
                    dp[leader][0] += dp[i][0];
                    dp[leader][1] += dp[i][0];
                    temp = Math.min(dp[i][1] - dp[i][0], temp);
                } else {
                    dp[leader][0] += dp[i][1];
                    dp[leader][1] += dp[i][1];
                    temp = 0;
                }
            }
            
            dp[leader][0] += temp;
        }
    }
    
    public static int solution(int[] sales, int[][] links) {
        int answer = 0;
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        int[][] dp = new int[sales.length+1][2];
        
        for (int i=0;i<links.length;i++) {
            if (map.containsKey(links[i][0])) {
                map.get(links[i][0]).add(links[i][1]);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(links[i][1]);
                map.put(links[i][0], list);
            }
        }
        
        rf(1, map, sales, dp);
        answer = Math.min(dp[1][0], dp[1][1]); 
        
        return answer;
    }
}