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

프로그래머스 매출 하락 최소화 [2021 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/72416

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

문제 풀이

• 문제 해결을 위해 다음의 시나리오를 DFS로 구현하였습니다.
• 각 사람별로 자신이 워크숍에 참석할 경우와 참석하지 않을 경우의 손해 비용을 계산합니다.
  • 자신이 leaf node인 경우
    • 내가 참석하지 않을 경우 -> 0원 
    • 내가 참석할 경우 -> 나의 하루평균 매출액
  • 자신이 leaf node가 아닌 경우
    • 내가 참석하지 않을 경우, 이 경우에는 다음과 같이 두 가지의 시나리오가 있습니다.
      • 자신의 팀원 중 워크숍에 참석할 경우에 더 이득인 팀원이 있을 경우
      • 참석할 경우에 이득인 팀원이 없지만 내가 참석하지 않기 때문에 팀원 중 한 명이 반드시 참석해야 하는 경우
    • 내가 참석할 경우
  • DFS로 위의 시나리오를 계산하면 결국 루트 노드가 참석할 경우와 참석하지 않을 경우 중 최소 손해 비용이 정답이 됩니다. 
• 코드의 주석을 보시면서 위의 시나리오를 다시 한번 보시면 이해가 쉬울 것 같습니다!

코드

#include <vector>
#include <unordered_map>

using namespace std;

unordered_map<int, vector<int>> team;

// pair<int,int> -> first:참석하지 않을 경우, second:참석할 경우
pair<int,int> dfs(vector<int> &sales, int member) {
    if(team.find(member) == team.end()) // leaf node
    	return {0, sales[member-1]}; // first:0, second:나의 하루평균 매출액
    else {
        int sum = 0, min_diff = 1e9;
        bool flag = false;
        
        for(auto mem: team[member]) {
            auto res = dfs(sales, mem);
				
            // 손해 비용이 최소가 되도록 팀원들 행동(참석 or 불참) : 여러명이 참석하는 것은 상관 없음
            sum += min(res.first, res.second); 
            
            /*
            ret.first(참석하지 않을 경우 손해비용) >= ret.second(참석할 경우 손해비용)
            -> 해당 팀원은 참석하지 않을 경우에 손해비용이 더 큼 = 워크숍에 참석할 경우 더 이득인 팀원이 있음
            */
            if(res.first >= res.second) flag = true;
            
            /*
            이 경우는 내가 참석하지 않을 때 나의 팀원 중 한 명이 반드시 워크숍에 참석해야 하는 상황
            그렇다면 손해의 차이가 가장 적은 팀원을 워크숍에 보냄
            (워크숍에 참석하거나 불참하거나 큰 차이가 없는 팀원)
            */
            min_diff = min(min_diff, res.second - res.first);
        }
        
        if(flag) return {sum, sales[member-1] + sum};
        else return {sum + min_diff, sales[member-1] + sum};
    }    
}

int solution(vector<int> sales, vector<vector<int>> links) {
    
    for(auto link: links) {
        team[link[0]].push_back(link[1]);
    }
    
    auto res = dfs(sales, 1);    
    
    return min(res.first, res.second);
}

실행 결과