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

문제 설명

유통 전문 회사 "카카오상사"는 여러 개의 팀으로 구성된 조직도를 가지고 있으며, 직원들은 팀장과 팀원으로 나뉘어 있습니다. CEO는 항상 팀장이며, 특정 직원은 두 개의 팀에 속할 수도 있습니다. 모든 팀이 최소 1명 이상의 직원을 워크숍에 참석시키면서, 참석하는 직원들의 하루평균 매출액의 합을 최소로 하는 방법을 찾아야 합니다.

---

제한 사항

• 직원 수는 2 이상 300,000 이하입니다.
• 직원의 하루평균 매출액은 0 이상 10,000 이하입니다.
• 조직도는 트리 구조로 주어집니다.

---

해결 방법

알고리즘: 동적 프로그래밍 (트리 DP)

1. 트리를 DFS 방식으로 탐색하며 하위 노드부터 최적 값을 계산합니다.
2. 각 노드는 참석하는 경우와 참석하지 않는 경우 두 가지 상태를 가집니다.
   • dpOn: 해당 노드가 참석하는 경우의 최소 비용
   • dpOff: 해당 노드가 참석하지 않는 경우의 최소 비용
3. 노드가 참석하면, 모든 하위 노드의 최소값을 더합니다.
4. 노드가 참석하지 않을 경우, 적어도 하나의 하위 노드는 반드시 참석해야 하므로 추가적인 비용을 계산합니다.
5. 최종적으로 루트 노드에서 min(dpOn, dpOff) 값을 반환합니다.

---

시간 복잡도

• DFS 탐색을 한 번 수행하므로 O(N)의 시간 복잡도를 가집니다.

---

구현 코드

function solution(sales, links) {
  const n = sales.length;
  const children = Array.from({ length: sales.length + 1 }, () => []);

  for (const [p, c] of links) {
    children[p].push(c);
  }

  function dfs(node) {
    let dpOn = sales[node - 1];
    let dpOff = 0;
    let hasOn = false;
    let extra = Infinity;

    for (const child of children[node]) {
      const [childOn, childOff] = dfs(child);

      dpOn += Math.min(childOn, childOff);

      if (childOn <= childOff) {
        dpOff += childOn;
        hasOn = true;
      } else {
        dpOff += childOff;
        extra = Math.min(extra, childOn - childOff);
      }
    }

    if (children[node].length && !hasOn) {
      dpOff += extra;
    }

    return [dpOn, dpOff];
  }

  const [on, off] = dfs(1);
  return Math.min(on, off);
}