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

2021 카카오 코딩 테스트 문제입니다.

 

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

문제 확인

 

dfs, 그리디로 풀 수 있지만 depth가 깊어지면 stack의 모든 상황을 확인하기 때문에 느리므로 트리 dp로 풉니다.

 

풀이

 

dp 배열을 dp[현재 노드 번호][선택 상태]로 둡니다.

선택 상태는 현재 노드가 워크숍에 참가 여부로 두고 조건을 고려합니다.

• dp[cur_idx][0] : 현재 노드가 워크숍에 참가하지 않을 때 팀의 최소비용, 자식 노드 중 하나 이상 워크숍에 참가가 필요합니다.
• dp[cur_idx][1] : 현재 노드가 워크숍에 참가할 때 팀의 최소비용, 자식 노드가 워크숍에 참가하지 않아도 상관없습니다.

다음 상태를 고려하여 식을 세워보면 다음과 같습니다.

 

말단 직원인 리프 노드는 팀장이 아니므로 dp[cur_idx][1] 만을 자신의 비용으로 채우면 됩니다.

 

현재 노드가 팀장인 경우를 생각해 봅시다.

현재 노드가 워크숍에 참가하는 경우 :

dp[cur_idx][1] = 모든 자식들의 dp 값 0, 1 중에서 작은 수 "min(dp[child][0], dp[child][1])" 들의 합

 

현재 노드가 워크숍에 참가하지 않는 경우 : 

이러한 경우는 한 가지 더 고려해야 합니다.

• 모든 자식 노드 dp값에서 워크숍에 참가하지 않는 경우가 최소일 경우, 즉 모든 child에 대하여 dp[child][0] < dp[child][1]인 경우 : 자식 중 손해 비용이 최소가 되는 경우의 팀을 강제로 참여시켜야 합니다. 이 경우 추가로 발생하는 비용은 참석하지 않았다가 참석을 하게 되면 발생하는 차액인  dp[child][1] - dp[child][0] 이 됩니다.
• 자식노드 dp값 중 하나라도 참가하는 경우가 최소인 경우, 즉 위의 경우를 하나라도 위배하는 경우 : 현재 노드가 워크숍에 참가하는 경우처럼 최솟값만을 더해주면 됩니다.

 

식으로 표현하게 되면 다음과 같습니다.

for(auto child : edge[cur])

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

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

if(dp[child][0] 만이 선택된다면)

   dp[cur][0] += min( (dp[child_1][1] - dp[child_1][0]) ~ (dp[child_1][1] - dp[child_1][0]))

 

코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int dp[300001][2];//1참가, 0 불참
vector<int> *sale;
vector<int> edge[300001];
void dfs(int cur) {
    dp[cur][1] = (*sale)[cur - 1];
 
    if (!edge[cur].empty()) {//팀장인 경우 자식노드가 있음을 이용
        for (auto next : edge[cur]) 
            dfs(next);
        
        int min_val = 0x7fffffff;
        for (auto next : edge[cur]) {
            if (dp[next][0] < dp[next][1]) {
                dp[cur][0] += dp[next][0];
                dp[cur][1] += dp[next][0];
                min_val = min_val > dp[next][1] - dp[next][0]
                    ? dp[next][1] - dp[next][0] : min_val;//참가 여부에 따른 차이의 최소비용을 구함
            }
            else {
                dp[cur][0] += dp[next][1];
                dp[cur][1] += dp[next][1];
                min_val = 0;//자식노드에 참가한 인원이 생기면 0으로 변경
            }
        }
        if (min_val != 0x7fffffff)//모든 자식노드가 참가하지 않았다면 최소비용을 더해 강제로 하나의 팀을 참여시킴
            dp[cur][0] += min_val;
    }
        
}
int solution(vector<int> sales, vector<vector<int>> links) {
    sale = &sales;
    for (auto &t : links) 
        edge[t[0]].push_back(t[1]);
    
    dfs(1);
 
    return dp[1][0] > dp[1][1] ? dp[1][1] : dp[1][0];
}
int main() {
    vector<int> s = { 14, 17, 15, 18, 19, 14, 13, 16, 28, 17 };
    vector<vector<int>>    l = { {10, 8}, {1, 9}, {9, 7}, {5, 4}, {1, 5}, {5, 10}, {10, 6}, {1, 3}, {10, 2} };
 
    cout << solution(s, l);
 
}
 

 

정확성 테스트

 

테스트 1 〉	통과 (0.01ms, 10.5MB)
테스트 2 〉	통과 (0.01ms, 10.5MB)
테스트 3 〉	통과 (0.01ms, 10.4MB)
테스트 4 〉	통과 (0.02ms, 10.5MB)
테스트 5 〉	통과 (0.07ms, 10.6MB)
테스트 6 〉	통과 (0.15ms, 10.6MB)
테스트 7 〉	통과 (0.41ms, 11.3MB)
테스트 8 〉	통과 (0.67ms, 11.6MB)
테스트 9 〉	통과 (1.37ms, 12.4MB)
테스트 10 〉	통과 (17.54ms, 34.1MB)
테스트 11 〉	통과 (20.50ms, 37MB)
테스트 12 〉	통과 (23.88ms, 41.6MB)
테스트 13 〉	통과 (26.90ms, 46.3MB)
테스트 14 〉	통과 (31.14ms, 50.9MB)
테스트 15 〉	통과 (40.62ms, 58.6MB)
테스트 16 〉	통과 (44.76ms, 63.5MB)
테스트 17 〉	통과 (59.62ms, 70.8MB)
테스트 18 〉	통과 (64.37ms, 75.4MB)
테스트 19 〉	통과 (57.24ms, 80.2MB)
테스트 20 〉	통과 (63.27ms, 82.9MB)
테스트 21 〉	통과 (0.01ms, 10.6MB)
테스트 22 〉	통과 (0.01ms, 10.4MB)
테스트 23 〉	통과 (0.01ms, 10.4MB)
테스트 24 〉	통과 (0.01ms, 10.5MB)
테스트 25 〉	통과 (0.01ms, 10.5MB)
테스트 26 〉	통과 (0.01ms, 10.5MB)
테스트 27 〉	통과 (0.02ms, 10.5MB)
테스트 28 〉	통과 (0.01ms, 10.5MB)
테스트 29 〉	통과 (0.01ms, 10.3MB)
테스트 30 〉	통과 (0.01ms, 10.5MB)
테스트 31 〉	통과 (0.01ms, 10.5MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0