Programmers - 매출 하락 최소화

Programmers 의 매출 하락 최소화 문제 풀이

---

문제

매출 하락 최소화

트리 구조에서 자식 노드를 가진 팀장 과 부모 노드를 가진 팀원 으로 나뉜다. 각 팀에서 한 명씩 불러야 할 때, 불러낸 각 노드의 매출합을 최소화 하는 문제입니다. 두 팀에 속하는 노드를 부를 경우 그 노드만으로 두 팀에서 각출한 것으로 치는 조건이 있습니다.

보통 트리가 등장하는 문제는 root 나 leaf 에서 어떻게 풀어야 할 지 고민하다 보면 해답이 보이는데, 이 문제는 쉽게 구상이 되지 않았습니다.(그러고보니 Level 4 문제는 처음 풀어보기도 했고…)

이 문제가 어려웠던 이유는 단순한 트리 문제처럼 모든 노드를 단순 순회하는 것으로 문제가 풀리지 않기 때문입니다. 이번 문제는 각 노드를 순회하되, 그 노드를 선택할지 말지도 고민됩니다. 어떤 노드를 선택하게 되면 전체적인 결과에도 영향을 미치기 때문에, 경우의 수를 나누고 그 경우를 기록해둬야 했습니다.

경우의 수를 기록하는 기법을 메모이제이션 (memoization), 타뷸레이션 (tabulation) 혹은 이런 개념을 포함하는 동적 계획법 (dynamic programming) 이라고 합니다. 이제 중요한 건 어떤 것을 기록해야 하는지 와 기록한 내용을 토대로 어떻게 구현해야 할 지가 되겠습니다.

해답 (2차원 배열 메모)

동적 계획법으로 풀어야 한다는 것을 알고 나서, 메모이제이션을 활용하기로 했습니다. 그러면 뭘 메모해둬야 할까요?

이 문제의 트리를 단순한 경우만 가지고 생각해보면, 어떤 subtree 에서의 정답이 루트 노드가 포함 되냐 마냐에 따라서만, 전체 트리일 때 정답에 영향을 미치는 것을 알 수 있습니다. 팀장 노드에서 팀원 노드 전부가 참여하지 않는 경우엔 반드시 팀장 노드가 참여해야 한다는 조건이 있기 때문입니다. (생각해보면 이외의 특별한 조건은 없다는 것을 알 수 있습니다.)

따라서 메모를 두 가지 합니다. (따라서 메모를 위한 데이터는 2차원 배열로 합니다.)

1. 해당 노드가 참여했을 때, subtree의 정답
2. 해당 노드가 불참했을 때, subtree의 정답

다시 말하지만 이 두가지 외엔 상위트리가 고려할 내용이 없다는 것이 중요합니다. 무엇을 메모해야 하는지가 정해지면 해답이 자연스럽게 보이기 때문입니다. 이를 이용한 코드는 아래와 같습니다.

import java.util.ArrayList;
class Solution {
    static ArrayList<Integer>[] edges;
    static int[] nodes;
    public int solution(int[] sales, int[][] links) {
    nodes = new int[sales.length + 1];  // node list
    for(int i = 1; i < nodes.length; i++){
      nodes[i] = sales[i-1];
    }
    edges = new ArrayList[sales.length + 1];
    for(int i = 0; i < nodes.length; i++){
      edges[i] = new ArrayList<Integer>();
    }
    for(int[] arr : links){
      edges[arr[0]].add(arr[1]);
    }
    dp = new int[nodes.length][2];

    calc(1);
    int answer = Math.min(dp[1][0], dp[1][1]); // CEO 포함인 경우 vs 미포함인 경우
    return answer;
  }

  static int[][] dp;
    // case = 0 팀장(자신) 선택
    // case = 1 팀원 선택

  private void calc(int node){

    for(int child : edges[node]){
      calc(child);
    }

    // postorder 
    int childSum = 0;
    int absenceSum = 0;
    for(int child : edges[node]){
      childSum += Math.min(dp[child][0], dp[child][1]); // 일단 작은거 더하는데...
      absenceSum += dp[child][1];
      // 둘 중에 작은 것 더하면 되는 거 아니야?
      // 그러다가 child 가 전부 선택 안되면 안되거든. (최소 하나는 선택 되어야 함.)
    }
    dp[node][0] += nodes[node] + childSum; // 팀장이 선택되면 전부 선택 안되도 상관 없음.
    if(childSum == absenceSum && edges[node].size() != 0) { // 팀장이 선택 안되는 경우 혹시 child 가 전부 선택이 안되는 케이스를 위해
      childSum = Integer.MAX_VALUE;
      for(int presentChild : edges[node]){
        int tmpSum = 0;
        for(int child : edges[node]){
          if(presentChild == child) tmpSum += dp[presentChild][0];
          else tmpSum += dp[child][1];
        }
        childSum = (childSum > tmpSum)? tmpSum : childSum;
      }
    }
    dp[node][1] += childSum;
  }
}

이 코드로 푸는데 성공 했지만, 1차원 메모로도 풀 수 있다는 것을 발견해서, 추가로 써봅니다.

해답 (1차원 메모)

Programmers 에 제출된 Java 해답 중 맨 위의 답안이 1차원 메모만 쓰고 있었습니다. 제가 위에 코드를 짤 때 생각하기론 아래 두가지 경우를 상위 트리가 고려해줘야 했습니다.

1. 해당 노드가 참여했을 때, subtree의 정답
2. 해당 노드가 불참했을 때, subtree의 정답

그래서 한 노드당 두가지 정보를 가지는 2차원 트리를 선택했는데, 1차원 메모만 쓰는 답안이 있어서 깜짝 놀랐어요. 코드를 곰곰히 살펴보니, 메모는 한가지만 고려하고 있습니다. 그렇다는 건…

1. (노드 선택 했든 말든) subtree의 정답

이것만 고려해도 괜찮았다는 건데, 코드를 보면서 고민을 좀 해보니 그렇긴 했습니다. 사실 이 풀이에서도 노드를 선택하는 경우와 하지않는 경우를 고려하긴 했습니다. 상위 트리에서, 다음 두 가지 상황을 고려하고 있습니다.

1. 팀장을 선택하지 않았을 때, 팀원 중 하나를 반드시 선택하고, 그 팀원의 하위 팀원에서 메모를 가져온다.
2. 팀장을 선택한 경우엔 따로 신경 쓸 조건이 없으므로, 단순하게 팀원들의 메모를 가져온다.

이렇게 짜 놓으면 앞서 설명한 것 처럼 상위 트리가 팀원의 메모 2개를 알아야 할 필요는 없는 대신, 두 단계 밑의 메모를 확인해야 합니다. 상당히 멋진 풀이라고 생각합니다.😄 게다가, 이해하기 쉬운 걸 보니 제 풀이보다 깔끔하게 쓰셧네요. 😢

import java.util.*;

class Solution {
    int memos[];
    public int solution(int[] sales, int[][] links) {
        Node nodes[] = new Node[sales.length+1];
        for(int i = 0; i < sales.length; i++)
            nodes[i+1] = new Node(sales[i], i+1);

        for(int[] link : links)
            nodes[link[0]].add(nodes[link[1]]);

        memos = new int[sales.length+1];
        Arrays.fill(memos, -1);

        return recursion(nodes[1]);
    }

    int recursion(Node node){
        if(node == null) return 0;
        if(memos[node.num] != -1)
            return memos[node.num];
        if(node.childs.size() == 0) return 0;

        int min = Integer.MAX_VALUE>>1;

        int sum = 0;
        for(int i = 0; i < node.childs.size(); i++){
            sum = 0;
            for(int j = 0; j < node.childs.size(); j++){
                if(i == j) continue;
                sum += recursion(node.childs.get(j));
            }
            for(Node child : node.childs.get(i).childs) {
                sum += recursion(child);
            }
            min = Math.min(min, sum+node.childs.get(i).sales);
        }
        sum = 0;
        for(Node child : node.childs)
            sum += recursion(child);
        min = Math.min(min, sum+node.sales);
        memos[node.num] = min;
        return min;
    }

    class Node{
        int sales;
        int num;
        List<Node> childs = new ArrayList<>();
        Node(int sales, int num){
            this.sales = sales;
            this.num = num;
        }
        void add(Node node){
            childs.add(node);
        }

    }
}