[프로그래머스] 2021 카카오공채 7번 매출하락 최소화-가장 쉽게 트리 dp로 푸는법, 쉬운설명

문제 링크

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

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

풀이 아이디어

우선 트리dp의 기본적인 풀이 방법을 알고 있다고 가정하고 작성한다.

해당 유형을 안풀어 봤을 때 hqjang.tistory.com/104?category=913845 를 참고할 것.

 

풀이의 핵심은 한 그룹에서 '최소 한명' 이 워크숍에 참석해야 한다는 것이다.

따라서 케이스는 두가지로 나뉜다.

 

1. 그룹장이 워크숍에 참석하는 경우 -dp[n][1]

2. 그룹장이 워크숍에 참석하지 않는 경우 - dp[n][0]

 

두 가지 경우는 완벽한 독립사건이므로 다이나믹 프로그래밍의 적용이 가능하다.

dp[n][0]은 해당 사원(n)이 포함 안됐을 때 최솟값, dp[n][1]은 해당 사원(n)이 포함 됐을 때 최솟값으로 정의하였다.

 

1. 그룹장이 워크숍에 참석하는경우

1.번의 경우는 2.번보다 우선 처리하기 쉽다.

다만 조심해야 하는 경우가, 예시 3번처럼 그룹장과 그룹원이 모두 참석하는 경우가 최솟값을 가질 때가 있는 것이다.

그룹장만 참석하는 경우보다, 그룹장과 그룹원 모두 참석하는 경우가, 그 그룹에서는 값이 더 클지 몰라도 전체적으로 따져봤을때 값이 더 작은 경우가 있다는 것이다.

따라서 dp 업데이트시 다음과 같이 진행되어야 된다.

dp[n][1] += min(dp[child][0],dp[child][1]);

 

2. 그룹장이 워크숍에 참석하지 않는 경우

2.번의 경우에는 그룹장이 워크숍에 참석하지 않으므로, 반드시 그룹원이 워크숍에 참석해야 된다.

이 사실을 먼저 인지하고 가자.

 

최솟값을 구하는 것이므로, 역시나 dp[child][0]과 dp[child][1] 중에서 더 작은 값을 더하면 되지만, 조건이 붙는다.

여기서 다시 2가지 케이스가 나오게 된다.

 

2-1. 한번이라도 dp[child][1]이 더해지게 되는 경우(그룹원이 1명이상 워크숍 가는경우)

최솟값을 더하다 보니, 그룹원이 워크숍에 참석하는 경우가 더해졌다!

그러면 완전 땡큐다. 그 값으로 dp[n][0]을 업데이트하면 된다.

그치만..

 

2-2. 전부 dp[child][0]이 더해진 경우(그룹원 한명도 워크숍 안가는경우)

이러면 위에 '인지'하라고 한 조건에서 벗어나게 된다.

따라서 그룹원을 한명 워크숍에 보내야 한다.

누구를 보내야 할까? 당연히

안보내는 것과 보내는 것을 비교해 봤을때, cost가 가장 덜 커지는 직원을 보내야 한다!

 

나는 cost 차이를 벡터에 넣고, 정렬해서 가장 앞 인덱스 값을

더해줌으로써 해결했다.

if(tree[n].size()>0){
        if(issumed) dp[n][0]=tmpsum;
        else{
            sort(tmpvec.begin(),tmpvec.end());
            dp[n][0]=tmpsum+tmpvec[0];
        }
    }

조심해야 할게 저 사이즈 검사를 안하면 코드가 안돌아가게 된다.

그룹원 자체가 한명이라도 있어야 하기 때문이다.

 

전체 코드는 다음과 같다.

코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector<int> tree[300001];
int dp[300001][2];
bool visited[300001];
//dp[][0]은 해당 사원이 포함 안됐을 때 최솟값, dp[][1]은 해당 사원이 포함 됐을 때 최솟값
void find(int n,const vector<int> &sales){
    dp[n][1]= sales[n-1];
    visited[n]=true;
    for(int i=0; i<tree[n].size(); i++){
        int child = tree[n][i];
        if(visited[child]) continue;
        find(child,sales);
        dp[n][1] += min(dp[child][0],dp[child][1]);
    }
    int tmpsum=0;
    bool issumed=false;
    vector<int> tmpvec;
    for(int i=0; i<tree[n].size();i++){
        int child=tree[n][i];
        if(dp[child][1]<dp[child][0]){
            issumed=true;
            tmpsum+=dp[child][1];
        }
        else{
            tmpvec.push_back(dp[child][1]-dp[child][0]);
            tmpsum+=dp[child][0];
        }
    }
    if(tree[n].size()>0){
        if(issumed) dp[n][0]=tmpsum;
        else{
            sort(tmpvec.begin(),tmpvec.end());
            dp[n][0]=tmpsum+tmpvec[0];
        }
    }
}

int solution(vector<int> sales, vector<vector<int>> links) {
    int answer = 0;
    for(auto a:links){
        tree[a[0]].push_back(a[1]);
    }
    find(1,sales);
    answer=min(dp[1][0],dp[1][1]);
    cout<<dp[1][0]<<" "<<dp[1][1];
    return answer;
}