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

문제 링크 : programmers.co.kr/learn/courses/30/lessons/72416

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

문제 유형

Tree DP, Greedy

 

2021 카카오 블라인드 코딩 테스트의 7번 문제이다.

문제의 '팀장'이 곧 서브트리의 root 노드임을 캐치했다면, 이 문제가 각 서브트리에서 최소 하나의 노드를 선택한 경우의 최소 가중치를 묻는 문제임을 알 수 있다. 단, 이 서브트리는 root와 그 자식 노드로만 이루어져 있다.

백준 2213 트리의 독립집합과 꽤 비슷한 문제이다. 이 문제와는 팀장이 참석해도(선택돼도) 여전히 그 자식 노드들이 선택될 수 있다는 차이가 존재한다.

각 노드는 선택되거나, 선택되지 않는 두 가지 경우가 존재하므로 다음과 같이 케이스를 분류할 수 있다.

 

① 팀장이 참석하는 경우 (서브트리의 root가 선택된 경우)

이 경우에는 팀원 전원이 참석하지 않아도 이미 팀장이 참여했기 때문에 문제의 조건을 만족한다.

따라서 서브트리 각 자식 노드들에 대해 선택하거나, 선택하지 않은 경우의 최소 가중치를 모두 구해 작은 값들만을 더해주면 된다.

 

② 팀장이 참석하지 않는 경우 (서브트리의 root가 선택되지 않은 경우)

각 자식 노드의 참석/불참시 가중치를 구해 더 작은 값을 취할 때, 하나라도 참석 시 가중치가 더 적어 선택된다면 문제가 없다.

하지만 만약 모든 자식 노드에 대해 불참 시의 가중치가 더 작아 선택되지 않게 된다면, 이는 문제가 된다.

각 팀마다 최소 한 명씩은 참석해야 하는 조건을 만족하지 못하기 때문이다. 따라서 자식 노드들 중 하나를 강제로 선택해야 한다.

이 과정에서 Greedy한 방법을 사용한다. 바로 (참석 시 가중치 - 불참 시 가중치)의 값이 가장 작은 노드를 선택하는 것이다. 이미 참석/불참에 대한 가중치를 미리 구해 놓은 상황에서는 반드시 이 값의 차이가 적은 노드를 강제로 선택해야  최종 결과가 최소가 된다.

 

[코드]

#include <string>
#include <vector>
#include <algorithm>
 
#define INF 999999999
 
using namespace std;
 
vector<int> val, adj[300001];
int dp[300001][2];      //0 : 선택 안함, 1 : 선택함
 
int get_dp(int node, int pnode, int sel){
    if(dp[node][sel] != 0) return dp[node][sel];
    int ret = 0, min_diff = INF;
    bool join = false;
    
    //리프 노드인 경우
    if(node != 1 && adj[node].size() == 1) 
        return dp[node][sel] = sel ? val[node - 1] : 0;
    
    for(int i = 0; i < adj[node].size(); i++){
        int child = adj[node][i];
        if(child == pnode) continue;
        
        //현재 node에게 자식들이 존재한다면, node는 반드시 그 팀의 팀장이다.
        //각 자식들에 대해 선택한 경우와 선택하지 않은 경우 중 작은 경우를 결과로 반환한다.
        int res_sel = get_dp(child, node, 1);
        int res_nosel = get_dp(child, node, 0);
        ret += min(res_sel, res_nosel);
        
        if(res_sel < res_nosel) join = true;
        else{
            //강제 선택을 위해 두 값의 차이를 저장
            min_diff = min(min_diff, res_sel - res_nosel);
        }
    }
    
    if(sel) ret += val[node - 1];
    else{ 
        //현재 노드를 선택하지 않은 경우, 반드시 자식 노드들 중 최소 하나는 선택해야 함
        if(!join) ret += min_diff;
    }
    
    return dp[node][sel] = ret;
}
 
void make_conn(vector<vector<int>> links){
    for(int i = 0; i < links.size(); i++){
        int f = links[i][0];
        int s = links[i][1];
        adj[f].push_back(s);
        adj[s].push_back(f);
    }
}
 
int solution(vector<int> sales, vector<vector<int>> links) {
    int answer = 0;
    
    val = sales;
    
    make_conn(links);
    answer = min(get_dp(1, 0, 1), get_dp(1, 0, 0));
    
    return answer;
}