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

🥹 풀이 시작 전에...

AI 추천 문제 풀었다가 우울해졌다.

이 문제를 볼 때, 일단 트리로 접근해야하는 건 확신했다.
그래서 DFS로 풀어야겠다고 생각하고 열심히 시도해봤다.

그런데 아무리 생각해봐도 직원 배열이 최대 30만개인데,
DFS로 하면 100%, 500%, 1000% 시간 초과가 발생할 게 뻔했다.
그래서 고민 끝에 알고리즘 힌트라도 얻고자 풀이를 찾아봤다.

힌트를 보니 드는 생각은
아니, AI는 도대체 어떤 분석으로 내가 이 문제를 풀 수 있다는 결론을 어떻게 내린거야....?
이 문제는 트리 DP로 풀어야 한다는데, 트리 DP는 처음 들어봤다ㅎ

이건 내가 혼자 풀 수 있는 게 절대 아니라는 걸 깨닫고 트리 DP의 원리를 공부해서 겨우 풀었다.
문제 다 풀고 확인하니까 무려 Lv4에 정답률이 12%였다..

아래의 풀이는 힌트 70%, 내 머리 30%가 합쳐진 결과이다.
원리 덕분에 풀 수 있었기 때문에 내 머리는 30% 정도라고 생각했다.
(실은 30%도 많은 듯..)

◼️ 문제

매출 하락 최소화

1. 문제 설명

2. 제한사항

3. 입출력

◼️ 풀이

🧠 알고리즘

내가 힌트로 참고한 글에 의하면 트리 DP로 풀었다고 한다.
트리도 알고 DP도 아는데, 트리 DP는 뭘까...?ㅠㅠㅠ
이름만 듣기엔 감이 어느정도 오긴 했지만, 이미 몇시간 째 문제를 부여잡고 있던 나에겐 이해가 공부가 절실하게 필요했다.

DP (Dynamic Programming)

DP의 특징은 큰 문제를 작은 문제로 나누어 푼다는 점이다.
작은 문제의 답을 먼저 구한 다음 작은 문제의 답을 이용해 큰 문제를 구하는 방식이다.

트리 DP

그렇다면 트리 DP는 무엇일까.
큰 트리를 작은 트리로 나누어 문제를 해결하는 방식인 것이다.
작은 트리를 활용해 큰 트리의 최종적인 답을 구하는 방식이기 때문에,
리프에서 루트 방향으로 문제를 해결해가면 된다.

이 문제에서는 dp로 해결하는 과정에서,
현재 팀장이 참석할 경우와 현재 팀장이 참석하지 않을 경우에 대해 각각 최소값을 구하는 것이 핵심이다.

✏️ 전반적인 풀이과정

1. 팀장과 팀원의 정보가 담긴 links 배열을 하나씩 확인하며, 조직도를 트리 형태로 만든다.
2. treeDP 함수를 이용해 워크숍에 참석하는 직원들이 최소 매출액을 갖는 결과를 찾아낸다. (재귀)
   2-1. 만약 현재 팀장의 팀원의 dp에 대한 정보가 없을 경우, 팀원의 dp 정보부터 구한다.
   2-2. 현재 팀장이 참석하지 않을 경우에 대한 최소값을 구한다.
   2-3. 현재 팀장이 참석할 경우에 대한 최소값을 구한다.

📃 풀이과정 상세 설명

재귀 함수로 리프에서 루트 방향으로 구하기

treeDP 함수를 통해 현재 팀장이 참석할 경우와 참석하지 않을 경우에 대한 매출액을 구하기 위해서는
팀원들의 dP 결과 이미 존재해야 한다는 가정이 필요하다.

팀원들의 dp 결과가 없다면, 팀원들의 dp부터 계산하는 방식으로 구현하기 위해 재귀를 택했다.
이렇게 하면, 최종적으로 가장 리프노드부터 dp를 계산하여 최종적으로 루트노드의 dp를 계산하게 된다.

// treeDP 함수 일부
const children = tree[index]

children.forEach((child) => {
  if (!dp[child]) treeDP(sales, tree, dp, child)
})

현재 팀장이 참석하지 않을 경우 최소 매출액

최소 매출액 = 팀원들의 최소값

우선 팀원들이 각각 참석할 때와 참석하지 않았을 때의 매출 최소액을 구해야 한다.
팀원들 배열을 돌면서 dp[0]과 dp[1] 중 작은 값만 선택해 계산하면 될 것이다.

위의 케이스에서 팀원 중 최소 한 명이라도 참석을 하면 문제가 없겠으나,
팀원 모두 참석을 하지 않으면 문제가 생긴다. 현재 팀장도 참여를 안 하기 때문이다.

그래서 위의 계산을 진행하면서 한 명이라도 참석을 하는지도 함께 확인을 해야 한다.
만약 아무도 참석하지 않을 경우 최소 매출액을 위해서 한 명만 참석할 때의 케이스를 구하고 그 중 가장 최소값으로 현재 팀장의 dp[0]을 확정지어야 한다.

현재 팀장이 참석할 경우 최소 매출액

최소 매출액 = 팀원들의 최소값 + 현재 팀장 매출액

위와 같이 팀원 모두가 참석하지 않을 경우를 굳이 확인하지 않아도 된다.
팀장이 참석하는 것이 확정되었기 때문이다.

따라서 팀원들 배열을 돌면서 작은 값들의 합과 현재 팀장의 매출액까지 합하면 된다.

마무리

제일 리프노드부터 루트노드(CEO)까지의 dp를 모두 구했다.
dp[0]과 dp[1] 중 작은 값을 고르면 그것이 최소 매출액이다.

💻 코드

function solution(sales, links) {
  const tree = {}
  const dp = {}
  links.forEach((link) => {
    const [leader, member] = link
    if (!tree[leader]) tree[leader] = []
    if (!tree[member]) tree[member] = []
    tree[leader].push(member)
  })
  treeDP(sales, tree, dp, 1)
  return Math.min(...dp[1])
}

function treeDP(sales, tree, dp, index) {
  dp[index] = [0, 0]
  const children = tree[index]
  children.forEach((child) => {
    if (!dp[child]) treeDP(sales, tree, dp, child)
  })
  
  // dp[index][0] 구하기 - 1
  let isAttend = false
  dp[index][0] = children.reduce((sum, child) => {
    if (dp[child][0] < dp[child][1]) return (sum += dp[child][0])
    isAttend = true
    return (sum += dp[child][1])
  }, 0)
  
  // dp[index][0] 구하기 -2
  if (!isAttend) {
    let minimum = Infinity
    for (let i = 0; i < children.length; i++) {
      let sum = 0
      for (let j = 0; j < children.length; j++) {
        if (i !== j) sum += dp[children[j]][0]
        else sum += dp[children[j]][1]
      }
      minimum = Math.min(minimum, sum)
    }
    if (minimum !== Infinity) dp[index][0] = minimum
  }
  
  // dp[index][1] 구하기
  dp[index][1] =
    children.reduce((sum, child) => (sum += Math.min(...dp[child])), 0) + sales[index - 1]
}

너무 열받아 하면서 푼 덕분에 트리 DP는 절대 안 잊을 것 같다^_^