EunSung.log

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

7 min read

Notice

문제 정보

해설

Notice

이하의 내용은 카카오테크 공식 홈페이지의 해설과 해당 해설을 보고 정리한 내용을 바탕으로 작성됨

DP를 잘 활용할 수 있어야 풀 수 있는 문제다.

DP는 상향식(bottom-up) 접근 방식으로, 핵심은 1) 문제를 더 작은 문제로 나누고 2) 앞에서 계산한 결과를 저장해뒀다가 나중에 사용한다는 것이다.

이 문제도 마찬가지로 리프 노드부터 하나하나 방문하면서 그때 그때의 최적해 (최소 하루평균 매출액의 합)를 계산해 나가는 식으로 푼다. (정확히는 서브트리에 대한 최적해를 구해 최종적으로 전체 트리에 대한 최적해를 알아내는 것.)

우선 DP를 위해 다음과 같은 배열 dp를 정의한다.

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

공식 해설에서는 dp를 계산하기 위해 보조 배열인 sum_child를 정의한다. 이 sum_child[i]는 i번 노드의 자식 노드들이 모두 최적의 선택을 했을 때의 하루 평균 매출액의 총합을 말한다.

이 sum_child를 이용하면 dp를 다음과 같이 구할 수 있다.

  • dp[i][1] = sales[i] + sum_child[i]
  • dp[i][0]
    1. i의 모든 자식 노드 k에 대해 dp[k][0] > dp[k][1]을 만족하는 k가 있는 경우
      • dp[i][0] = sum_child[i]
    2. i의 모든 자식 노드 k에 대해 dp[k][0] > dp[k][1]을 만족하는 k가 없는 경우
      • dp[i][0] = sum_child[i] + min(dp[k][1] - dp[k][0])

dp[i][1]은 구하기 쉽다. i번 노드가 워크숍에 참석하는 경우이므로 sum_child[i]에 i번 노드의 하루 평균 매출액을 더하면 된다.

dp[i][0]은 두 가지 경우로 나눠서 생각해야 한다.

우선 i의 모든 자식 노드 k에 대해 dp[k][0] > dp[k][1]을 만족하는 k가 있는 경우에 대해 살펴보자.

i의 모든 자식 노드 k에 대해 dp[k][0] > dp[k][1]을 만족하는 k가 있다는 얘기는, i의 팀원 중 워크숍에 참석하는 팀원이 있다는 의미다. (dp[k][0] > dp[k][1]을 만족한다는 것은, 참여했을 때의 하루 평균 매출액의 총합이 더 작다는 것이므로.)

그러므로 dp[i][0]은 그냥 sum_child[i]가 된다.

반면 i의 모든 자식 노드 k에 대해 dp[k][0] > dp[k][1]을 만족하는 k가 없는 경우는 i의 팀원 중 워크숍에 참석하는 팀원이 없다는 의미다.

즉, i가 워크숍에 참석하지 않으면서, 팀원 중에서도 워크숍에 참석하는 인원이 없다는 것으로, 이는 모든 팀에서 최소 한 명 이상 워크숍에 참석한다는 조건을 만족시키지 못한다.

따라서 팀원 중에 한 명을 강제로 워크숍에 참석시켜야 한다. 그렇다면 이 때 최석의 선택은 참석했을 때 하루 평균 매출액의 총합이 가장 적게 증가하는 팀원을 참석시키는 것이다.

그러므로 dp[i][1]은 sum_child[i] + min(dp[k][1] - dp[k][0])이 된다.

코드

import java.util.*;
 
class Solution {
    ArrayList<ArrayList<Integer>> tree;
    int[][] dp = new int[300001][2];
    
    public int solution(int[] sales, int[][] links) {
        tree = new ArrayList<>();
        
        for(int i = 0; i < sales.length + 1; i++)
            tree.add(new ArrayList<>());
        
        for(int[] link : links) 
            tree.get(link[0]).add(link[1]);
        
        dfs(1, sales);
        
        return Math.min(dp[1][0], dp[1][1]);
    }
    
    public void dfs(int cur, int[] sales) {
        dp[cur][0] = 0;
        dp[cur][1] = sales[cur - 1];
        
        if(tree.get(cur).size() == 0)  // 리프 노드인 경우
            return;
        
        int minDiff = Integer.MAX_VALUE;        
        for(int child : tree.get(cur)) {
            dfs(child, sales);
            
            // 자식 노드의 최적해 누적
            dp[cur][0] += Math.min(dp[child][0], dp[child][1]);
            dp[cur][1] += Math.min(dp[child][0], dp[child][1]);
            
            // 현재 노드의 자식 노드 중 워크숍에 참가하는 노드가 없으면
            if(dp[child][0] < dp[child][1]) 
                // 자식 노드가 워크숍에 참가할 때 발생하는 추가 비용 계산
                // 그 비용이 최소가 되는 것을 선택
                minDiff = Math.min(minDiff, dp[child][1] - dp[child][0]);
            else
                minDiff = 0;
        }
        
        // 현재 노드가 불참하는 경우의 최종 계산
        dp[cur][0] += minDiff;
        
        return;
    }
}

공식 해설을 기반으로 내가 작성한 코드다.

우선 리프 노드부터 dp를 계산해야 하므로 DFS로 트리를 순회했다.

앞선 풀이에서 sum_child는 자식 노드들이 모두 최적의 선택을 했을 때의 하루 평균 매출액의 총합이라고 말했다. 그리고 이는 i번 노드가 참가하든 말든 dp[i] 계산에 필요한 값이므로 Math.min()을 사용해 더해주었다.

백링크