[ 프로그래머스 매출 하락 최소화 (Lv4) ] (C++)

프로그래머스의 매출 하락 최소화(Lv4) 문제이다.

 

[ 문제풀이 ]

한 팀에 최소 1명 이상의 직원이 워크숍에 참가해야 할 때, 매출 손실을 최소화하기 위해서 워크숍 참가하는 직원들의 매출액의 합이 최소가 되는 값을 구해야 하는 문제이다.

먼저, 주어진 직원들을 관리하는 것 부터 정답을 도출하는 과정까지 진행해보자.

 

#1. 직원의 관리

이 문제에서는 조직도를 통해서 직원들의 상관관계를 표현하고 있다.

1명의 CEO가 존재하고 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있다. 그렇다면 이를 어떻게 관리할지에 대해서 부터 이야기를 해보자.

본인은 간단하게 vector배열을 이용해서 팀장과 팀원의 관계를 저장하고 관리해 주었다.

vector<int> Node[] 라는 vector배열을 선언해 주었는데, Node[A]에 { B , C , D }라는 원소가 삽입되어 있다면 이는

"팀장이 A인 팀에게 속해있는 팀원 리스트는 [ B , C , D ]  입니다" 를 의미한다.

코드로 표현하면 다음과 같이 표현할 수 있다.

void Make_Relation(vector<int> sales, vector<vector<int>> links)
{
	for (int i = 0; i < links.size(); i++)
	{
		int Parent = links[i][0];
		int Child = links[i][1];
		Node[Parent].push_back(Child);
	}
}

간단하게 vector배열을 통해서 표현을 한 것이지만, 마치 그 형태는 트리의 형태와 비슷하다.

왜냐하면, 내 부모가 되는 Node도 또 다른 부모를 가지고 있고, 그 위에 또다른 부모를 가지고 있는 이런 형태로 구성되어 있기 때문에 마치 트리 형태로 직원들이 관리되고 있다고 생각할 수 있다.

 

#2. 접근법

본인은 이 문제를 DFS + Dynamic Programming 방식을 이용해서 접근해 보았다.

그리고 DP 과정을 위해 사용되는 수식부터 하나 알아보자.

F[A][B] = C 라는 수식을 사용할 것인데, 이 수식에서 'B'에 해당하는 인덱스는 크기가 2인 부분이다.

즉, B에 들어올 수 있는 값으로는 0 or 1 2개만 존재한다는 것이다.

이 수식의 의미는 다음과 같다.

F[A][0] = C : A번 사람이 워크숍에 참석하지 않을 때, 워크숍에 참석하는 직원들의 매출액의 최소값은 C원입니다.

F[A][1] = C : A번 사람이 워크숍에 참석했을 때, 워크숍에 참석하는 직원들의 매출액의 최소값은 C원입니다.

그리고 이 수식들을 리프노드들부터 하나씩 채워갈 것이다.

리프노드라는 것은 트리에서 자식을 가지고 있지 않은 노드들을 의미한다.

1번 노드가 루트노드가 되는 전체 트리를 세분화 시켜서 여러 개의 서브트리들고 나누고, 해당 서브트리들에서도 가장 작은 노드인 리프노드부터 채워나감으로써 정답을 구하기 위해서 리프노드들 부터 탐색을 할 것이다.

즉 ! 만약 위의 수식을 제대로 잘 채웠다면 우리가 원하는 정답은 Min(F[1][0] , F[1][1]) 중에 있을 것이다.

위의 식을 풀어서 설명하면, 회사의 CEO가 워크숍에 참가했을 때 드는 매출의 최소액 vs CEO가 워크숍에 참가하지 않았을 때 드는 매출의 최소액 중 더 작은 값을 정답으로 채택한다는 것이다.

 

#3. Leaf Node

#2에서 리프노드부터 탐색을 한다고 했으니, 리프노드들 부터 탐색을 해보자. 그런데 어떻게 리프노드들 부터 탐색을 할까?? 본인은 리프노드로 접근하는 것을 재귀를 통해서 접근하였다.

1번 Node를 시작으로 재귀함수를 호출한 후, 자식노드가 없을 때 까지 계속해서 재귀함수를 호출해주는 것이다.

그렇다면 결국 리프노드에 접근할 수 있게 될 것이다.

그럼 리프노드에 접근했다면 이제 이 노드들부터 수식을 한번 채워보자.

#3 - 1) 리프노드가 워크숍에 참가하는 경우

먼저 리프노드가 워크숍에 참가하는 경우부터 알아보자.

리프노드 같은 경우에는 그 밑에 더 이상의 자식이 없기 때문에, 본인이 참가를 하게 된다면 본인의 매출액만큼의 비용이 들 것이다. 즉, 이를 수식으로 적어보면 다음과 같이 표현이 가능하다.

F[리프노드의번호][1] = sales[리프노드의번호]

위의 수식을 풀어서 설명해보면, "해당 리프노드가 워크숍에 참가했을 경우, 매출액의 합의 최소값은 해당 리프노드의 매출액입니다." 가 된다. 왜냐하면 ! 아직까지 수식이 하나도 완성된 것이 없고 리프노드들부터 채워나가는 과정이기 때문에 위와 같은 수식이 완성될 수 있다. DP풀이에서 초기식이 되는 역할과도 비슷한 것이다.

#3 - 2) 리프노드가 워크숍에 참가하지 않는 경우

반대로 리프노드가 워크숍에 참가하지 않는 경우는 어떻게 될까 ??? 그냥 0원이 될 것이다.

F[리프노드의번호][0] = 0

위와 같이 리프노드들의 값을 설정해줄 수 있다.

 

#4. 리프노드가 아닌 노드

리프노드가 아닌 노드들에 대해서 지금부터 이야기해보자. 리프노드가 아닌 노드라는 것은 자식을 가지고 있는 노드들이라는 것을 의미한다. 지금부터는 계산이 조금은 복잡해진다.

마찬가지로 워크숍에 참가하는 경우와 참가하지 않는 경우로 나눠서 이야기를 해보자.

 

#4 - 1) 해당 노드가 워크숍에 참가하는 경우

먼저, 리프노드가 아닌 노드에 해당하는 노드가 워크숍에 참가하는 경우를 생각해보자.

분명히 리프노드가 아니기 때문에 팀장의 역할을 하면서 팀원의 역할을 동시에 하는 노드일 것이다.

그런데 ! 이 노드가 워크숍에 반드시 참가를 한다고 생각을 해보자. 그럼 다음과 같은 정보들을 알 수 있다.

1. 이 직원이 워크숍에 참가하므로, 이 직원 밑에 있는 다른 팀원들이 워크숍에 참가하든 말든 관심이 없다.

2. 이 직원이 워크숍에 참가하므로, 워크숍에 참가하는 직원들의 매출액의 합에 이 직원의 매출액이 더해질 것이다.

이 2가지 정보를 알 수 있다.

이 직원이 워크숍에 참가하면 해당 직원의 팀원들이 워크숍에 참가하든 말든 상관이 없어진다. 왜냐하면 이 직원이 참가를 함으로써 이 팀에서는 최소 1명이 워크숍에 참가하는 것이 되어버리기 때문이다.

그럼 예를 들어서 이 직원을 'A', 이 직원의 밑에 있는 팀원들이 [ B , C ]가 있다고 가정해보자.

일단 워크숍에 참가하는 직원들의 매출액에 sales[A]는 반드시 더해질 것이다. 그럼 이 때 어떻게 해야 최소가 될까 ??

바로 , Min(F[B][0], F[B][1]) + Min(F[C][0], F[C][1]) 이 매출액의 최소가 될 것이다.

팀원들 중에 누군가가 반드시 워크숍에 참가를 해야 하는 경우가 아니기 때문에, 팀원들은 워크숍을 참가할때와 참가하지 않을 때의 매출액을 비교해서 더 작은 매출액을 갖는 쪽으로 선택을 해주면 된다.

그 중간과정에서 "워크숍을 참가할 때 매출액이 더 작은 팀원"이 발생한다하더라도, 상관이 없다. 왜냐하면 팀에서 최소 1명 이상은 워크숍에 참가해야 한다는 조건에 위배되지 않기 때문이다.

for (int i = 0; i < Node[현재노드].size(); i++)
{
	int Child = Node[현재노드][i];
	Sum += Min(F[Child][0], F[Child][1]);
}
F[현재노드][1] = Cost[현재노드] + Sum;

즉 위와같이 구현을 해줄수가 있다.

 

#4 - 2) 해당 노드가 워크숍에 참가하지 않는 경우

이제 이 경우에 대해서 이야기를 해보자.

여기는 4-1)의 과정과는 조금 다르게, 다음과 같은 조건이 필요하다.

"팀원 중, 반드시 한 명은 워크숍에 참가를 해야 한다." 바로 이 조건이다.

왜 이런 조건이 필요할까 ?? 현재노드가 워크숍에 반드시 참가하지 않을 경우를 계산하고 있기 때문이다.

현재노드가 워크숍에 반드시 참가하지 않는다는 것은, 팀원 중에 반드시 한명 이상은 워크숍에 참가해야함을 의미한다.

그런데 ! 너무나도 운이 좋게도, 다음과 같은 경우가 발생한다고 생각해보자.

"팀원 중 한명이 워크숍에 참가하지 않았을 때의 매출액보다, 워크숍에 참가했을 때의 매출액이 더 적은 경우"

여기서 자꾸 매출액이 더 크니 작니 이런 이야기를 하는데 이게 단순히 워크숍에 참가하지 않았을 때는 0원, 워크숍에 참가했을 때는 sales[해당직원] 처럼 계산을 하는 것이 아니다.

여기서 이야기 하는 것은 "해당 직원이 워크숍을 참가 하거나 하지 않았을 때, 워크숍에 참가한 직원들의 매출액의 최소비용" 을 의미하는 것이다. 위에서 이야기한 수식 'F'를 설명할 때에도 "워크숍에 참가한 직원들의 매출액의 최소비용" 이라고 되어있다.

다시 본론으로 돌아와서, 팀원 중 한명이 워크숍에 참가하지 않았을 때 참석하는 직원들의 매출액의 합보다, 워크숍에 참가했을 때 참석하는 직원들의 매출액의 합이 더 작은 팀원이 있다고 가정해보자.

즉 ! 위의 수식으로 표현해보면 다음과 같은 상황인 것이다.

Min(F[팀원번호][0] , F[팀원번호][1]) = F[팀원번호][1]

그렇다면 ? 이 팀원은 반드시 워크숍에 참가시켜 주는 것이 이득이다. 왜 ? 그게 워크숍에 참석한 사람들의 매출액의 합이 최소가 되기 때문이다. 이 사람은 참가를 하지 않는 것보다 참가를 했을 때 회사 전체에 이득이 될 수 있는 사람이 되는 것이다. 즉 ! 팀장의 역할을 하고 있는 현재 노드가, 반드시 워크숍에 참가하지 않는다고 가정했을 때, 이런 팀원이 존재한다면 마음 편하게 워크숍에 참가하지 않을 수 있을 것이다.

코드로 표현하면 다음과 같다.

for (int i = 0; i < Node[현재노드].size(); i++)
{
	int Child = Node[현재노드][i];
	Sum += Min(F[Child][0], F[Child][1]);
	if (F[Child][0] >= F[Child][1]) Attend = false;
}

F[현재노드][1] = sales[현재노드] + Sum;
if (Attend == false) F[현재노드][0] = Sum;

위의 4-1)의 코드에서 조금 더 추가된 코드이다.

현재 노드의 팀원들을 탐색할 때, "워크숍에 참가하는 것이 더 이득인 팀원"을 찾는 과정이 중간에 조건문으로 추가가 되었다. 만약, 이러한 팀원들이 있다면 마음 편하게 워크숍에 참가하지 않아도 된다는 것을 의미하고, 이 때 매출액의 최소값은 가장 마지막 줄에 있는 F[현재노드][0] = Sum 이 된다.

Sum이라는 변수는 팀원들이 워크숍에 참가했을 때, 참가하지 않았을 때를 비교해서 매출액이 더 최소가 되는 경우들만 선택해서 모두 더해놓은 변수이다. 중요한 것은 이 "매출액이 더 최소가 되는 경우" 들에 "워크숍에 참가했을 때 매출액이 더 최소가 되는 팀원이 존재" 한다는 것이다. 이 경우에는 위와 같이 계산을 할 수 있다.

 

그런데 ! 정말 마음 편하지 못한 상황은 반대로, "모든 팀원들이 워크숍에 참가하지 않았을 때 매출액이 최소가 되는 경우" 이다. 이제부터 이 경우에 대해서 알아볼 것이다.

이 경우가 왜 마음이 편하지 못한 것일까 ?? 본론으로 돌아와보자면 우리는 지금 "현재노드가 반드시 워크숍에 참가하지 않는 경우"를 계산하고 있기 때문이다. 지금 내가 워크숍에 참가를 안할건데, 팀원들마저 다들 하나같이 워크숍에 참가하지 않을 때 매출액이 최소가 되는 상황인 것이다. 즉 ! "강제로 누군가를 워크숍에 억지로 보내야 한다" 는 상황인 것이다.

그럼 이 때는 누구를 억지로 워크숍에 보내는 것이 제일 좋을까 ???

당연하게도, "워크숍에 참가하지 않았을 때의 매출액과 워크숍에 참가했을 때의 매출액의 차이가 가장 작은 팀원"을 보내는 것이 가장 이득일 것이다. 왜냐하면 우리는 워크숍에 참가하는 직원들의 매출액의 합이 최소가 되는 금액을 찾아야 하는 상황이고, 이 상황속에서 팀원 한명을 억지로 보내야 한다면, 워크숍에 참가하더라도, 참가하지 않았을 때와의 금액이 가장 차이가 작게 나는 팀원을 보내는 것이 워크숍에 참가하는 직원들의 매출액의 합을 최소가 되도록 만들 수 있기 때문이다. 그럼 이 상황을 코드로 확인해보도록 하자.

01.	int Sum = 0;
02.	int Min_Cost = 987654321;
03.	bool Attend = true;
04.	for (int i = 0; i < Node[현재노드].size(); i++)
05.	{
06.		int Child = Node[현재노드][i];
07.		Sum += Min(DP[Child][0], DP[Child][1]);
08.		if (F[Child][0] >= F[Child][1]) Attend = false;
09.		Min_Cost = Min(Min_Cost, F[Child][1] - F[Child][0]);
10.	}
11.	
12.	F[현재노드][1] = sales[현재노드] + Sum;
13.	if (Attend == false) F[현재노드][0] = Sum;
14.	else F[현재노드][0] = Sum + Min_Cost;

이전에 나왔던 코드에서 조금 더 추가된 코드이다.

지금부터 이 코드들이 우리가 이야기한 내용 중 어디에 해당하는 내용들인지 정리해보고 마무리하자.

line 7)에 보면, 팀원들이 워크숍에 참가하는 경우 vs 참가하지 않는 경우를 비교해서 매출액이 더 작은 경우를 뽑아서 모두 더해주고 있다. 만약, 이 때 "워크숍에 참가하는 것이 더 이득인 팀원" 이 있다면, 즉 ! line8)의 조건문에 부합하는 팀원이 존재한다면, 'Attend'라는 변수를 통해서 "마음 편하게 워크숍에 참가하지 마세요!" 라고 말을 해주고 있다.

하지만 ! 마음 편하게 워크숍에 참가하지 못하는 경우를 대비해서 line9)에서는 "팀원들이 워크숍에 참가했을 때의 매출액 vs 워크숍에 참가하지 않았을 때의 매출액의 차이가 가장 작은 금액" 을 계산해 주고 있다.

line12)는 "내가 워크숍에 참가하니 팀원은 참가를 하든 말든 상관이 없다" 를 표현한 부분이다.

line13)은 "내가 워크숍에 참가하지 않을 것이지만, 워크숍에 참가하는게 더 이득인 팀원이 있는 상황"을 표현한 것이다.

line14)는 "내가 워크숍에 참가하지 않을 것이므로, 워크숍의 참가를 할 때와 하지 않을 때의 차이가 가장 작은 팀원을 억지로 워크숍에 보내는 상황"을 표현한 것이다.

그럼 line14)의 수식에 대해서 한번 알아보자. 예를 통해서 알아보자.

현재 노드 = A , 팀원 노드 = [ B , C ] 가 있다고 가정해보자.

그리고 ! "현재노드인 A는 워크숍에 반드시 참가하지 않을 것이지만, B, C 모두 참가하지 않는 것이 매출액이 최소가 되는 팀원들이라서, 이들 중 누군가를 억지로 보내야 하는 상황" 이라고 가정하자.

위의 코드에서 Sum이라는 변수에는 아마 다음과 같은 값들이 계산 되어질 것이다.

Sum = F[B][0] + F[C][0]

왜냐하면 B, C 모두 참가하지 않는 것이 더 이득인 팀원들이므로 위와 같은 수식이 적용될 것이다.

line8)에 있는 조건문에는 들어가지 못할 것이다. 현재 상황은 A가 마음 편하게 참가하지 않아도 되는 경우가 아니기 때문이다.

그런데, B와 C중에서 B가 워크숍에 참가했을 때와 아닐 때의 매출액의 차이가 더 작은 팀원이라고 가정해보자.

그럼 억지로 보내야 하는 팀원은 'B'가 된다는 것을 의미하게 된다. 그렇다면, 우리가 구해놓은 Sum은 다음과 같이 변해야 할 것이다.

Sum = F[B][0] + F[C][0] → Sum = F[B][1] + F[C][0]

위의 수식을 조금만 더 다르게 써본다면, Sum = F[B][0] + F[C][0] + F[B][1] - F[B][0] 가 되는 것이다.

여기서 "F[B][1] - F[B][0]"에 해당하는 값을 line9)에서 계산을 해주고 있다.

따라서 line14)에서 위와 같이 매출액이 계산이 되는 것이다.

 

이와 같이 매출액들을 모두 구했다면 우리가 원하는 최종적인 정답은 F[1][0] vs F[1][1] 중 더 작은 값에 저장되어 있을 것이다. 실제 코드에서는 우리가 이야기한 수식 'F'가 'DP'라는 식으로 적혀있습니다 !!

 

[ 소스코드 ]

#include <string>
#include <vector>
 
#define MAX 300010
using namespace std;
 
int DP[MAX][2];
vector<int> Node[MAX];
vector<int> Cost;
 
int Min(int A, int B) { return A < B ? A : B; }
 
void Make_Relation(vector<int> sales, vector<vector<int>> links)
{
    for (int i = 0; i < links.size(); i++)
    {
        int Parent = links[i][0];
        int Child = links[i][1];
        Node[Parent].push_back(Child);
    }
}
 
void DFS(int Cur)
{
    bool Leaf_Node = true;
    for (int i = 0; i < Node[Cur].size(); i++)
    {
        int Next = Node[Cur][i];
        Leaf_Node = false;
        DFS(Next);
    }
 
    if (Leaf_Node == true)
    {
        DP[Cur][0] = 0;
        DP[Cur][1] = Cost[Cur - 1];
        return;
    }
 
    int Sum = 0;
    int Min_Cost = 987654321;
    bool Attend = true;
    for (int i = 0; i < Node[Cur].size(); i++)
    {
        int Child = Node[Cur][i];
        Sum += Min(DP[Child][0], DP[Child][1]);
        if (DP[Child][0] >= DP[Child][1]) Attend = false;
        Min_Cost = Min(Min_Cost, DP[Child][1] - DP[Child][0]);
    }
    
    DP[Cur][1] = Cost[Cur - 1] + Sum;
    if (Attend == false) DP[Cur][0] = Sum;
    else DP[Cur][0] = Sum + Min_Cost;
}
 
int solution(vector<int> sales, vector<vector<int>> links) 
{
    int answer = 0;
    Cost = sales;
    Make_Relation(sales, links);
    DFS(1);
    answer = Min(DP[1][0], DP[1][1]);
    return answer;
}