[프로그래머스][level4] 매출 하락 최소화 (C++)

https://programmers.co.kr/learn/courses/30/lessons/72416

코딩테스트 연습 - 매출 하락 최소화

 

 

[난이도] level4
[유형] DP

[풀이]
sales 배열의 크기가 최대 300000 이므로 판매원을 참석시킬 수 있는 모든 케이스를
다 해보기에는 시간이 너무 오래걸리기 때문에 다이나믹 프로그래밍을 사용해야 합니다.

우선 주어진 입력을 이용해 2차원 tree vector에 tree[parent].push_back(child) 와 같이
트리 형식으로 저장해줍니다.

Top-Down 방식을 이용하였고 sol(n)은 DP[n]은 구하고 return 합니다.

DP 배열은 아래와 같이 간단히 정의합니다.
DP[n] : 루트가 n인 트리의 최소 비용.

루트가 n일때,  루트인 n 혹은 그 자식 노드중에 하나는 회의에 참석해야 합니다.
위의 케이스를 모두 계산해보고 그 중 최솟값을 DP[n]의 값으로 확정짓는 방식으로 DP[n]을 구합니다.

우선 풀이에 사용될 변수 v를 아래와  같이 정의합니다.
v : n의 자식 노드가 nxt일 때 모든 DP[nxt]의 합
v = sum(DP[nxt])

점화식은 아래와 같습니다.
DP[n] = 

        i) n을 회의에 참석 시킬 때,
            n을 참석 시킬 때 비용 sales[n]에 n의 자식 노드들의 최소비용을 더해주기만 하면 되므로
            v + sales[n] 이 됩니다.

        ii) n의 자식 중 하나인 nxt를 회의에 참석 시킬 때,
            root인 n은 참여하지 않았으므로 sales[n]은 더할 필요 없이
            일단 v 값에 sales[nxt]를 더해줍니다.
            v값은 업데이트 되면 안되므로 임시변수 t를 선언하였습니다.
            t = v+sales[nxt]

            여기서 v에 더해져 있던 sol(nxt) 값은 nxt가 회의에 참석 되는 것이 확정되었으므로
            t에 빼주어야 합니다. 왜냐하면 sol(nxt)에는 nxt가 참여한 경우, 참여하지 않은 경우가 모두
            포함되어 있기 때문입니다.
            t = v+sales[nxt]-sol(nxt)

            여기까지 해주면 nxt의 자식들이 nnxt라고 했을 때, sol(nnxt)의 값도 빠져버려 nxt 자식 트리들의
            비용은 반영이 안되어 버리기 때문에 sol(nnxt)의 값들은 다시 더해줘야 합니다.
            t = v+sales[nxt]-sol(nxt)+sum(sol(nnxt)) (nnxt는 nxt의 자식노드들)
            위의 t 값이 nxt를 회의에 참여 시켰을 때의 최솟값이 됩니다.

        만약 sol(n)에서 n의 자식이 없다면 회의에 참석할 필요가 없기 때문에 0을 return 합니다.

        최종 DP[n]은 i),ii) 케이스 둘에서 나온 값들 중에 최솟값이 됩니다.

 

#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;
vector<int> sales,tree[300001];
int dp[300001],inf=1<<31-1;
int sol(int n){
    if(tree[n].empty()) return 0;
    int& ret = dp[n];
    if(ret!=-1) return ret;

    ret=inf;
    int v=0;
    for(int nxt : tree[n]) v+=sol(nxt);
    ret=min(ret,v+sales[n-1]);
    for(int nxt : tree[n]){
        int t = v-sol(nxt);
        t+=sales[nxt-1];
        for(auto nnxt : tree[nxt]) {
            if(!tree[nnxt].empty()) t+=sol(nnxt);
        }
        ret=min(ret,t);
    }
    return ret;
}
int solution(vector<int> _s, vector<vector<int>> links) {
    sales = _s;
    memset(dp,-1,sizeof(dp));
    for(auto l : links) tree[l[0]].push_back(l[1]);
    return sol(1);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/매출_하락_최소화.cpp