2021 KAKAO Blind - 7. 매출 하락 최소화

목차

개요

설명

코드

 

개요

어떤 tree가 주어졌을 때, 임의의 node에서 자신 혹은 자식 노드들 중에서 하나만 선택하면서 그 선택의 비용의 최솟값은 얼마인가를 구하는 문제입니다.

 

이 문제는 Tree DP인데, 특정 노드를 선택하는 Tree DP 특징 중에 하나로는 자신의 노드가 선택 되었는지, 안되었는지 구분해서 구하는 문제가 많습니다. 각각의 배열을

• dpYes (dpYes[i]의 값은 i번째 node의 child를 모두 계산을 끝낸 뒤, 자신이 선택 되었을 때 그 비용)
• dpNo (dpNo[i]의 값은 i번째 node의 child를 모두 계산을 끝낸 뒤, 자신이 선택되지 않았을 때 그 비용)

로 구분하여 구하면 되겠습니다.

 

이 때, dpYes는 자식들을 순회하면서 min(dpYes[child], dpNo[child]) 값을 모두 더한 뒤, 자신의 비용을 더하면 됩니다.

 

$$dpYes[node] = \sum ^{child} {min(dpYes[k] , \ dpNo[k])} \ \ + \ \ sales[node]$$

 

반대로 dpNo는 자신을 고르지 않는 상황입니다. 이 때는 필수적으로 자식 중에 최소 1개를 골라야겠죠? 따라서, 자식을 모두 순회하면서 선택한 자식은 dpYes의 값을, 나머지 자식은 min(dpYes[child], dpNo[child])의 값을 취해 더하면 됩니다. 그리고 자식을 모두 순회한 뒤, 그 중 최솟값을 고르면 되지요.

 

$$dpNo[node] = min(dpYes[i] + \sum ^{child} _{child\neq\ i} min(dpYes[k], dpNo[k]))$$

 

마지막으로 이제 min(dpYes[1], dpNo[1]) 을 return하면 됩니다.

 

설명

위 설명에서 이해하기 어려운 점은 아마 "dpYes와 dpNo가 왜 저런 식으로 나타내어 지는가?"일 것입니다.

위 그림에서 붉은색 노드를 기준, 직관적으로 다음과 같이 구분할 수 있습니다.

 

1) 붉은색 노드가 선택 된 경우 (dpYes)

 

$$dpYes[node] = \sum ^{child} {min(dpYes[k] , \ dpNo[k])} \ \ + \ \ sales[node]$$

아래 초록색 노드(자식 노드)들도 각자 dpYes와 dpNo의 값을 갖고 있습니다. 그러나 붉은색 노드가 선택될 예정이므로 자식들은 선택이 되든, 안되든 상관이 없습니다. 결국 자식 노드 각각에서 dpYes[child]와 dpNo[child]중에 작은 값을 골라 누적하면 되지요.

다만, 자신이 선택되었으므로 자신을 선택한 비용을 더해야 합니다. (sales[node])

 

2) 붉은색 노드가 선택되지 않은 경우

 

$$dpNo[node] = min(dpYes[i] + \sum ^{child} _{child\neq\ i} min(dpYes[k], dpNo[k]))$$

이 경우는 자식 중에 최소 하나가 선택되어야 합니다. 즉, 자식 중에 하나를 dpYes로 직접 골라야 하는 것이지요. 하나만 고르면 나머지 자식은 선택이 되든, 안되든 상관이 없습니다. 딱 하나만 dpYes로 골라보면 됩니다.

 

그러나 어떤 자식을 선택하는 것이 최소 비용이 될지는 모릅니다. 따라서 자식들을 순회하면서 하나씩 dpYes로 설정해보고, 그들 값 중에 최소를 골라야 하는 것이지요.

 

이번에는 카카오 예제를 통해 살펴볼까요?

 

Step 1: Leaf Nodes and Group D

먼저 leaf 노드 들은 위 식을 따라 dpYes[leaf] = sales[leaf], dpNo[leaf] = 0이 될 것입니다.

이제 D 그룹을 살펴봅시다. 만약 10번 노드가 선택된다면, 자식은 선택이 되어도, 안되어도 상관이 없습니다. 결국 자식들 각각의 최소비용의 합을 구하면 되는것이죠. 여기서는 0입니다. 다음 자신을 선택하였으므로 sales[10]을 더하면 됩니다.

즉, dpYes[10] = 0+sales[10] = 17이 됩니다.

 

만약 10번 노드를 선택하지 않는다면, 자식들 중에서 최소 하나는 선택이 되어야 합니다. 따라서 자식들을 순회하면서 각각 하나씩만을 선택해보고, 그 중에 최소값을 dpNo에 적으면 됩니다.

여기서는 14, 16, 17 인데 14가 가장 작으므로 dpNo[10] = 14 가 됩니다.

 

B 그룹은 간단하므로 넘어가겠습니다.

 

Step 2: Group C

이제 C그룹을 살펴봅시다. 5번 노드가 되겠네요.

 

dpYes[5]는 자신을 선택하는 것이므로 자식들은 선택되어도, 안되어도 상관이 없습니다. 따라서 자식 노드들 각각의 최솟값의 합을 구하면 됩니다.

dpYes[5] = min(dpYes[4], dpNo[4]) + min(dpYes[10], dpNo[10]) + sales[5] = 0 + 14 + 19= 33

 

dpNo[5]는 자신을 선택하지 않는 것이므로 자식들을 하나씩 선택해봐야 합니다.

4번을 선택한다면 그 비용은 dpYes[4] + min(dpYes[10], dpNo[10]) = 32가 되겠지요.

10번을 선택한다면 그 비용은 dpYes[10] + min(dpYes[4], dpNo[4]) = 17이 됩니다.

따라서 dpNo[5] = min(32, 17) = 17이 됩니다.

 

Step 3: Group A

 

이제 마지막 Group A를 살펴봅시다. 마찬가지로 dpYes[1]은 자식들 각각의 최솟값의 합 + sales[1] = 13 + 17 + 0 +14 = 44

dpNo[1] 은 각 자식들을 하나씩 선택해본 뒤 최솟값을 선택하면 됩니다. min(28+17+0, 13+33+0, 13+17+15) = 45

 

최종적으로 정답은 min(dpYes[1], dpNo[1]) = 44가 됩니다.

 

코드

카카오 7번 문제이지만 6번 문제보다 코드가 짧은 듯 합니다.

• 제 코드에서는 한 가지 트릭이 있습니다. 반드시 이렇게 짤 필요는 없으나 연산을 조금 줄이고자 dpNo를 계산할 때 dpYes의 계산 값을 활용합니다. 어차피 자식 노드 하나 빼고는 나머지 전부 최솟값을 고르는 것이 동일하기 때문이지요.
• dfs, bfs 모두 상관이 없습니다. 노드 처리 순서는 오로지 dpYes와 dpNo를 계산할 때, 자식 노드들이 모두 연산이 마쳐있기만 하면 됩니다.

#include <string>
#include <vector>
#define IMAX 2147483647
using namespace std;

vector<int> graph[300001];
int dpNo[300001];
int dpYes[300001];
char visited[300001];

int min(int a, int b){
    return a > b? b : a;   
}
void dfs(int cur, vector<int> & sales){
    vector<int> childs;
    for(auto itr = graph[cur].begin(); itr != graph[cur].end(); itr++){
        if(!visited[*itr]){
            visited[*itr] = 1;
            childs.push_back(*itr);
            dfs(*itr, sales);
        }
    }
    int yes = 0, no = IMAX;
    for(auto itr = childs.begin(); itr != childs.end(); itr++){
        yes += min(dpYes[*itr], dpNo[*itr]);   
    }
    for(auto itr = childs.begin(); itr != childs.end(); itr++){
        int tmp = dpYes[*itr] - dpNo[*itr] > 0? dpYes[*itr] - dpNo[*itr] : 0;
        if(no > yes + tmp) no = yes + tmp;
    }
    dpYes[cur] = yes+sales[cur-1];
    dpNo[cur] = no == IMAX? 0 : no;
}

int solution(vector<int> sales, vector<vector<int>> links) {
    int answer = 0;
    for(auto itr = links.begin(); itr != links.end(); itr++){
        int a = (*itr)[0];
        int b = (*itr)[1];
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    visited[1] = 1;
    dfs(1, sales);
    answer = min(dpYes[1], dpNo[1]);
    return answer;
}