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

프로그래머스 매출 하락 최소화 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

배열에 각 직원들의 0 <= sales <= 10000 만큼의 매출액이 주어지며 배열의 크기는 직원의 수와 같습니다.
links 배열의 각 원소는 [a, b]이며 a는 팀장, b는 팀장이 관리하는 팀원입니다.
팀장과 팀원이 이루어진 팀에서 최소 한 명이 워크숍에 참여해야 하며, 참석하는 직원들의 하루평균 매출액의 합을 최소로 해야 합니다.
1번은 언제나 CEO이므로 무조건 팀장이 되며, 정답은 2^31 - 1 이하인 자연수임이 보장됩니다.

팀장과 팀원간의 최소값을 찾아가는 것이 중요해보입니다.

문제 풀이

편한 계산을 위해 주어진 간선들을 미리 배열에 연결해줍니다.

for(vector<int> v : links)
{
    team[v[0]].push_back(v[1]);
}
    
memset(dp, -1, sizeof(dp));

이번 문제는 DFS를 통하여 아래서부터 차근차근 계산을 시작하였습니다.
DFS를 통해 아래서부터 계산하면서 생각해야 되는 부분이 3가지가 있습니다.

1. 팀장이 워크숍에 참여한 경우
2. 팀장이 워크숍에 참여하지 못한 경우
3. 팀장이 워크숍에 참여하지 못하였지만, 팀원들도 같이 참가하지 못한 경우

1번의 경우는 팀원들이 워크숍에 참여한 경우와 참여하지 않은 경우 두 가지 중 더 적은 매출액을 가진 경우를 더해줍니다.
팀원들이 모두 워크숍에 참여하지 않더라도 팀장이 참여하기 때문에 괜찮습니다.

2번의 경우는 1번과 같이 팀원들이 워크숍에 참여한 경우와 참여하지 않은 경우 두 가지 중 더 적은 매출액을 가진 경우를 더해줍니다.
하지만 팀장도 팀원들도 모두 참여를 안해 팀에서 아무도 참여를 하지 않는 상황이 발생할 수 있습니다.
그러면 3번의 경우를 생각하여 팀장이 참여하지 않는 대신 팀원들 중 제일 매출액이 적은 팀원이 참여를 해야 합니다.

void dfs(int cur)
{
	//팀장이 아닌 경우의 값 설정
    dp[cur][0] = 0;
    dp[cur][1] = salesInfo[cur-1];
    if(team[cur].empty())   { return; }
    int ans = 0, minValue = 2100000000;
    
    for(int i = 0; i < team[cur].size(); i++)
    {
    	//참여 경우와 참여하지 못한 경우를 dp배열에 저장함.
        dfs(team[cur][i]);
        //참여하지 못한 경우가 매출액이 적을 경우
        if(dp[team[cur][i]][0] < dp[team[cur][i]][1])
        {
            dp[cur][0] += dp[team[cur][i]][0];
            dp[cur][1] += dp[team[cur][i]][0];
            //팀원이 모두 참여하지 못하는 상황을 생각하여 매출액이 적은 경우를 생각함.
            //dp[team[cur][i]][1]은 cur팀장의 팀원이 팀장을 맏았을 경우의 매출액
            //dp[team[cur][i]][0]은 cur팀장의 팀원이 팀장을 맏지 않았을 경우의 매출액
            minValue = min(minValue, dp[team[cur][i]][1] - dp[team[cur][i]][0]);
        }
        else//참여한 경우가 매출액이 적을 경우
        {
            dp[cur][0] += dp[team[cur][i]][1];
            dp[cur][1] += dp[team[cur][i]][1];
            //팀원이 팀장이 되어서 참여를 한 경우이므로 조건이 완료되었으니 만약을 위한 minValue값을 0으로 맞춰줌
            minValue = 0;
        }
    }
    //팀원이 모두 참여하지 못하는 상황이면 팀원 중 최솟값을 더해줌
    dp[cur][0] += minValue;
}

전체 코드

이번 문제는 다이나믹 프로그래밍을 써보고 배우는 문제였습니다.
난이도가 정말 어려워서 다른 사람들의 해설도 여러 번 보면서 이해하였습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<int> team[300001];
int dp[300001][2] = {0,};
vector<int> salesInfo;

void dfs(int cur)
{
    dp[cur][0] = 0;
    dp[cur][1] = salesInfo[cur-1];
    if(team[cur].empty())   { return; }
    int ans = 0, minValue = 2100000000;
    
    for(int i = 0; i < team[cur].size(); i++)
    {
        dfs(team[cur][i]);
        if(dp[team[cur][i]][0] < dp[team[cur][i]][1])
        {
            dp[cur][0] += dp[team[cur][i]][0];
            dp[cur][1] += dp[team[cur][i]][0];
            minValue = min(minValue, dp[team[cur][i]][1] - dp[team[cur][i]][0]);
        }
        else
        {
            dp[cur][0] += dp[team[cur][i]][1];
            dp[cur][1] += dp[team[cur][i]][1];
            minValue = 0;
        }
    }
    dp[cur][0] += minValue;
}

int solution(vector<int> sales, vector<vector<int>> links) {
    int answer = 0;
    salesInfo = sales;
    
    for(vector<int> v : links)
    {
        team[v[0]].push_back(v[1]);
    }
    
    memset(dp, -1, sizeof(dp));
    
    dfs(1);
    
    return answer = min(dp[1][0], dp[1][1]);
}

출저

https://school.programmers.co.kr/learn/courses/30/lessons/72416