프로그래머스 - 매출 하락 최소화

문제가 넘 어려워서 다른 분의 풀이를 참고하여 이해하였다

 

접근 과정

 

트리 dp

 

1. dp[k][0] - k팀의 팀장이 뽑히는 경우

2. dp[k][1] - k팀의 팀원이 뽑히는 경우

 

팀 이름은 팀장의 번호를 따라감

d[k][0]은 본인의 매출, d[k][1]은 0으로 세팅

 

 

1. 

내가 팀장으로 뽑힐 때

내 팀원이 팀장으로 뽑힐 때, 팀원으로 뽑힐 때 모두 고려해야 함

d[k][0] += min(d[child][0], d[child][1])

 

2.

이 경우 역시 d[child][0], d[child][1] 중 최소값을 전부 더해주면 되지만 두 가지 케이스로 나뉨

 

i) d[child][0]이 최소인 팀원이 하나라도 있을 때, 땡큐인 상황  1번과 똑같이 진행

d[k][1] += min(d[child[0], d[child][1])

 

ii) 모든 child가 d[child][1]이 최소일 때, 어쩔 수 없이 한명이 선택되어야 함

 

즉, d[k][1] += min(d[child[0], d[child][1])에서 전부 d[child][1]가 더해지는 경우에서

한 팀원이 선택되어 dp[child][1] 대신 d[child][0]이 더해져야 한다.

 

이때 d[child][0] - d[child][1]이 가장 작은 팀원을 선택해준다.

 

#include <string>
#include <vector>
#define INF 1e18
using namespace std;
 
vector<int> v[300001];
 
// dp[k][0] 팀장이 뽑히는 경우
// dp[k][1] 팀원이 뽑히는 경우
long long dp[300001][2];
 
void dfs(int cur){
    bool flag = false;
    
    for(int i=0; i<v[cur].size(); i++){
        int next = v[cur][i];
        
        dfs(next);
        
        dp[cur][0] += min(dp[next][0], dp[next][1]);
        dp[cur][1] += min(dp[next][0], dp[next][1]);
        
        if(dp[next][0] <= dp[next][1]) {
            flag = true;
        }
    }
    
    // 리프노드여도 리턴
    if(flag || v[cur].size()==0) return;
    
    // dp[cur][1] 갱신시 팀원 모두가 dp[next][1]이 최소일 때
    long long mm = INF;
    
    for(int i=0; i<v[cur].size(); i++){
        int next = v[cur][i];
        mm = min(mm, dp[next][0] - dp[next][1]);
    }
    
    dp[cur][1] += mm;
    
    return; 
}
 
int solution(vector<int> sales, vector<vector<int>> links) {
    int answer = 0;
    
    for(int i=0; i<sales.size(); i++){
        dp[i+1][0] = sales[i];
    }
    
    
    for(int i=0; i<links.size(); i++){
        v[links[i][0]].push_back(links[i][1]);
    }
    
    dfs(1);
    
    answer = min(dp[1][0], dp[1][1]);
    
    return answer;
}