72416. 매출 하락 최소화

프로그래머스 72416번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

코딩테스트 연습 - 매출 하락 최소화 | 프로그래머스 스쿨

풀이

아이디어

Level 4 문제 처음 풀어봤다… 너무 어려웠다.

삽질

처음 문제를 읽고 아래처럼 접근하면 될 것 같다고 생각했다.

• 팀 정보를 Map 또는 Set 구조를 저장해두고
• 각 팀마다
  • 팀장을 참석시키는 경우
  • 팀원 중 매출이 가장 적은 사람을 참석시키는 경우
  • 위 2가지 경우의 수로 나눠서 dp로 푼다.

하지만 이 접근은 서브트리 (하위 조직) 을 전혀 고려하지 못한 접근이었다. 사실 서브트리가 있다는 것을 생각을 못했었는데, 사실 상위 팀의 결정은 하위 팀에도 영향을 주는 문제였다. 아래 조직도를 예로 들어보면:

• A팀: 현숙, 옥순, 영숙
• B팀: 영숙, 정숙

상위의 A팀을 먼저 생각해보면 옥순의 매출액이 가장 작으므로 옥순만 참석하는 쪽으로 결정된다. (참석자의 매출액 총 합: 1) 그리고 B팀으로 내려와서 참석자를 결정해보면, 영숙이 더 매출액이 작으므로 영숙이 참석하는 쪽으로 결정된다. (참석자의 매출액 총 합: 11) 하지만 실제로 총 참석자의 매출액의 최솟값은 A팀과 B팀 통틀어서 영숙 1명만 참석하는 10이다.

이런 이유에서 단순히 2개의 경우의 수로만 나눌 것이 아니라 하위트리의 상황까지를 모두 고려해서 결정해야 하는 (쉽지 않은) 문제라는 것을 깨닫게 되었다…

아이디어 도출

문제를 다시 보면, 각 직원은 참석 또는 불참이라는 두가지 상태를 가질 수 있다. 그리고 상위 선택은 하위 선택과 강하게 영향을 주고받고 있음을 알 수 있다.

그래서 각 노드(직원) v에 대해서 아래 두 dp 배열을 정의했다.

• dp1[v] : v가 참석할 때 v 서브트리의 최소 비용
• dp0[v] : v가 불참할 때 v 서브트리의 최소 비용 (이 경우에는 자식 중 최소 1명이 반드시 참석해야 한다.)

dp 문제임이 분명해졌으므로 점화식을 설계해보자.

점화식 설계

여기서 “비용이 저렴하다” 라는 표현은 “워크샵에 참석함으로 인해서 제외되는 매출액이 적다”는 것을 의미한다. “매출액이 적다” 아님!

v가 참석하는 경우(dp1[v])엔 v 자신이 이미 참석했기 때문에 속한 팀의 조건은 자동으로 충족하게 된다. 따라서 자식들은 참석/또는 불참 중에서 더 싼 상태를 선택하면 된다. (참석하는 쪽이 하위 트리를 모두 고려했을 때 더 저렴한 선택일수도 있다.)

dp1[v] = sales[v] + Σ min(dp0[c], dp1[c])

문젠 v가 불참하는 경우이다… (너무 어렵습니다..) v가 불참하면 직속 팀원들 중 최소 1명은 무조건 참석해야 한다는 제약 조건이 생긴다. 우선 아무 제약이 없다고 생각하고, 직속 팀원들의 상태에 따른 최소 비용을 계산한다.

base = Σ min(dp0[c], dp1[c])

이 최소비용 base 상태에서 팀원들은 불참이거나 참석일 수 있다. 모든 팀원들이 불참일수도 있기 때문에, “최소 비용으로 골라 둔 상태에서 딱 한명만 참석으로 바꾸었을 때, 추가되는 비용이 가장 적은 팀원을 골라”줬다.

이렇게 추가되는 비용을 extra라고 했을 때:

extra(c) = dp1[c] - min(dp0[c], dp1[c])

나도 헷갈렸던 포인트라서 계속 덧붙이자면, 어떤 팀원은 참석하는 쪽이 이미 최솟값을 만드는 상태였을 수도 있다. 이런 경우에는 당연하게도 extra = 0일 것이다.

이렇게 extra를 구해서, dp0[v]의 값을 결정하면 된다.

dp0[v] = base + min(extra(c))

Bottom-up 접근

재귀로 구현해도 괜찮은데, 이 문제의 노드 수가 300,000개로 꽤 많았기 때문에 오버플로우가 날 수도 있겠다 생각했다. 그래서 stack을 이용해서 DFS 순서를 만들고 (order 배열), order를 역순으로 처리해서 postorder 효과를 만들어줬다.

const order = [];
const stack = [1];
while (stack.length) {
  const v = stack.pop();
  order.push(v);
  for (const c of children[v]) {
    stack.push(c);
  }
}

이렇게 해서 자식 dp를 먼저 계산하고, 이를 이용해서 부모 dp를 구해줬다.

코드

function solution(sales, links) {
  const n = sales.length;

  // 1) 인접 리스트 구성
  const children = Array.from({ length: n + 1 }, () => []);
  for (const [a, b] of links) {
    children[a].push(b);
  }

  // 2) 후위순회 준비
  // NOTE: order를 역순으로 처리해서 postorder 효과를 낸다.
  const order = [];
  const stack = [1];
  while (stack.length) {
    const v = stack.pop();
    order.push(v);
    for (const c of children[v]) {
      stack.push(c);
    }
  }

  // 3) dp 배열 준비 (1-indexed)
  // dp0: v가 참석했을 때의 워크숍 참석 인원의 총 하루 평균 매출액 최솟값
  // dp1: v가 참석하지 않았을 때의 워크숍 참석 인원의 총 하루 평균 매출액 최솟값
  const dp0 = new Array(n + 1).fill(0);
  const dp1 = new Array(n + 1).fill(0);

  // 4) Bottom-up DP 계산 (order를 역순으로 돌면서 후위순회)
  for (let i = order.length - 1; i >= 0; i--) {
    const v = order[i];
    const childs = children[v];

    // case 1) 리프인 경우 (순수 팀원인 경우)
    // - dp0[v] = sales[v] (본인이 참석)
    // - dp1[v] = 0 (본인 불참. 아래 팀이 없기 때문에 자식 중 한명이 꼭 참석해야 한다는 강제가 없다. 불참하면 끝.)
    if (childs.length === 0) {
      dp1[v] = sales[v - 1];
      dp0[v] = 0;
      continue;
    }

    // case 2) 팀장이고 팀원인 경우 (하위 팀이 있음)
    // a) 참석하는 경우 : 같은 팀의 다른 팀원들은 참석하든 안하든 상관 없음
    // -> dp1[v] = sales[v] + ∑ min(dp0, dp1)
    // b) 불참하는 경우 : 같은 팀의 다른 팀원 중 적어도 한명은 참석해야 함
    // -> 우선 모든 팀원들에서 가장 싼 상태를 더한 뒤 (sumMin)
    // -> 참석으로 돌렸을 때 비용이 가장 적게 추가되는 인원을 참석으로 돌린다. (extraMin)
    // -> dp0[v] = sumMin + extraMin
    let sumMin = 0;
    let extraMin = Infinity;

    for (const c of childs) {
      const m = Math.min(dp0[c], dp1[c]); // 참석하는 것과 안하는 것 중 최솟값
      sumMin += m;

      const extra = dp1[c] - m; // (참석으로 돌렸을 때 추가되는 비용)
      if (extra < extraMin) {
        extraMin = extra;
      }
    }

    dp1[v] = sales[v - 1] + sumMin;
    dp0[v] = sumMin + extraMin;
  }

  return Math.min(dp0[1], dp1[1]);
}