## 🌟 문제
[코딩테스트 연습 - 매출 하락 최소화 \| 프로그래머스 스쿨](https://school.programmers.co.kr/learn/courses/30/lessons/72416)
![[ac9a531c-efec-470e-9702-b0544cd1eb2c.png]]
트리 모양의 조직도가 주어진다.
CEO를 제외한 각 직원은
- 어떤 팀의 팀장
- 어떤 팀의 팀장이고 다른 팀의 팀원
- 어떤 팀의 팀원
이렇게 3가지 포지션을 갖게 된다.
각 팀에서 최소 1명씩을 뽑아서 워크샵에 참석시킬 때,
워크샵 참석 인원의 하루 평균 매출액 총 합의 최소를 구하는 문제
## 🌟 풀이
> Level 4 문제 처음 풀어봤다... 너무 어려웠다.
### 삽질
처음 문제를 읽고 아래처럼 접근하면 될 것 같다고 생각했다.
- 팀 정보를 Map 또는 Set 구조를 저장해두고
- 각 팀마다
- 팀장을 참석시키는 경우
- 팀원 중 매출이 가장 적은 사람을 참석시키는 경우
- 위 2가지 경우의 수로 나눠서 dp로 푼다.
하지만 이 접근은 **서브트리 (하위 조직)** 을 전혀 고려하지 못한 접근이었다. 사실 서브트리가 있다는 것을 생각을 못했었는데, **사실 상위 팀의 결정은 하위 팀에도 영향**을 주는 문제였다. 아래 조직도를 예로 들어보면:
![[61a11699-6e05-4737-a38e-111450240fe8.png|300]]
- A팀: 현숙, 옥순, 영숙
- B팀: 영숙, 정숙
상위의 A팀을 먼저 생각해보면 옥순의 매출액이 가장 작으므로 옥순만 참석하는 쪽으로 결정된다. (참석자의 매출액 총 합: 1)
그리고 B팀으로 내려와서 참석자를 결정해보면, 영숙이 더 매출액이 작으므로 영숙이 참석하는 쪽으로 결정된다. (참석자의 매출액 총 합: 11)
하지만 실제로 총 참석자의 매출액의 최솟값은 A팀과 B팀 통틀어서 영숙 1명만 참석하는 10이다.
이런 이유에서 단순히 2개의 경우의 수로만 나눌 것이 아니라 하위트리의 상황까지를 모두 고려해서 결정해야 하는 ~~(쉽지 않은)~~ 문제라는 것을 깨닫게 되었다...
### 아이디어 도출
문제를 다시 보면, 각 직원은 참석 또는 불참이라는 두가지 상태를 가질 수 있다. 그리고 상위 선택은 하위 선택과 강하게 영향을 주고받고 있음을 알 수 있다.
그래서 각 노드(직원) v에 대해서 아래 두 dp 배열을 정의했다.
- `dp1[v]` : v가 참석할 때 v 서브트리의 최소 비용
- `dp0[v]` : v가 불참할 때 v 서브트리의 최소 비용 (이 경우에는 자식 중 최소 1명이 반드시 참석해야 한다.)
dp 문제임이 분명해졌으므로 점화식을 설계해보자.
### 점화식 설계
> [!NOTE]
> 여기서 "비용이 저렴하다" 라는 표현은 "워크샵에 참석함으로 인해서 제외되는 매출액이 적다"는 것을 의미한다.
> "매출액이 적다" 아님!
**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 효과를 만들어줬다.
```javascript
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를 구해줬다.
## 전체 코드
```javascript
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]);
}
```