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

 

 

 

문제

문제 설명

 

풀이

 

처음에 문제를 읽고 경우를 생각해 봤다. A, B팀의 매출액 하락이 최소가 되기 위해서는 A팀의 최소, B팀의 최소를 더한 값과 A, B팀 둘 다 속한 인원이 워크숍을 들었을 때의 값 중 최솟값을 비교하면 된다.

문제는 팀이 2개가 아니라 여러 개일 경우이다.

​

팀이 여러개일 경우 경우를 나눠서 생각해봤다.

A팀부터 A팀의 하위에 있는 팀들이 전부 워크숍을 듣는 경우를 생각해보자.

(A팀의 팀원은 B, C, D 3명이 있다고 가정, 팀원들이 다른 팀의 팀장인지는 모름)

​

[A팀장이 워크숍을 받는 경우]

 

A팀의 팀장이 워크숍을 받는 경우는 B, C, D 는 워크숍에 참가해도 되고 참가하지 않아도 된다.

그러므로 B의 하위에 있는 팀들이 전부 워크숍을 참가했을 때 최소비용만 알면 된다.

 

마찬가지로 C, D도 하위에 있는 팀들이 전부 워크숍을 참가했을 때 최소비용을 구하면 A팀의 팀장이 무조건 워크숍을 받는 경우에는 (A팀 팀장의 매출액) + (B팀 하위 최솟값) + (C팀 하위 최솟값) + (D팀 하위 최솟값) 을 더한 값이 최소값이 된다.

​

[A팀장이 워크숍을 받지 않는 경우]

 

이 경우 A팀의 팀장이 워크숍을 받지 않는다고 하면, B, C, D 중 한명은 무조건 교육을 받아야 한다.

그러면 이 경우 최솟값은 아래와 같이 구할 수 있다.

(하위 팀 중 한 팀의 팀장만 워크숍을 받으면 나머지 팀의 팀장은 워크숍을 받아도 되고 받지 않아도 된다.)

​

1.

B팀의 팀장이 워크숍을 받는 경우 중 최솟값 + Min(C팀의 팀장이 워크숍을 받는 경우의 최솟값, C팀의 팀장이 워크숍을 받지 않는 경우의 최솟값) + Min(D팀의 팀장이 워크숍을 받는 경우의 최솟값, D팀의 팀장이 워크숍을 받지 않는 경우의 최솟값)

​

2.

C팀의 팀장이 워크숍을 받는 경우 중 최솟값 + Min(B팀의 팀장이 워크숍을 받는 경우의 최솟값, B팀의 팀장이 워크숍을 받지 않는 경우의 최솟값) + Min(D팀의 팀장이 워크숍을 받는 경우의 최솟값, D팀의 팀장이 워크숍을 받지 않는 경우의 최솟값)

​

3.

D팀의 팀장이 워크숍을 받는 경우 중 최솟값 + Min(B팀의 팀장이 워크숍을 받는 경우의 최솟값, B팀의 팀장이 워크숍을 받지 않는 경우의 최솟값) + Min(C팀의 팀장이 워크숍을 받는 경우의 최솟값, C팀의 팀장이 워크숍을 받지 않는 경우의 최솟값)

​

위 세가지 경우 중 최솟값이 A팀장이 워크숍을 받지 않는 경우의 최솟값이 된다.

이를 반복해서 구하면 하위팀의 최솟값들을 이용해 현재 팀의 비용의 최솟값을 구하면 결국 모든 팀이 워크숍에 참가했을 때의 최솟값을 구할 수 있다.

​

팀장의 직책을 갖고 있는 사람이 두개의 팀에 속해 있을 수 있기 때문에 팀장을 기준으로 삼아 DP로 풀 수 있는 문제였다.

​

​

[아이디어 정리]

 

1. 현재 팀부터 하위 팀의 워크숍 비용의 최솟값을 현재 팀 팀장이 워크숍을 가는 경우, 가지 않는 경우로 나눈다.

​

2. 현재 팀의 팀장이 워크숍을 가는 경우 하위 팀들은 각각 팀의 팀장이 가는 경우의 최솟값과 팀장이 가지 않는 경우의 최솟값 중 더 작은 워크숍 비용을 선택해 더한다.

​

3. 현재 팀의 팀장이 워크숍을 가지 않는 경우 하위 팀들 중 한 팀의 팀장은 워크숍을 들어야 하고, 그 외의 팀은 팀의 팀장이 가는 경우의 최솟값과 팀장이 가지 않는 경우의 최솟값 중 더 작은 워크숍 비용을 선택해 더한다.

​

4. 최종적으로 가장 상위 팀 (팀장의 팀원번호가 1인 팀)의 팀장이 가지 않는 경우, 팀장이 가는 경우 중 최솟값을 return한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <cmath>
using namespace std;

const int MAX_VALUE = pow(2,31)-1;
int myNumUse[3000001]={0,}; // 무조건 사용
int myNumNotUse[3000001]={0,}; // 무조건 사용X
int myMinValue[3000001]={MAX_VALUE,};
int isCalc[3000001]={0,};
vector<int> sales(3000001);
vector<vector<int>> childList(3000001);
void calc(int num){
    if (childList[num].size()>0){
        int myUse = sales[num-1]; // 내 그룹 상위를 무조건 쓰는 경우
        int myNotUse =0; // 내 그룹장을 무조건 안쓰는 경우
        int myNotUseValue=MAX_VALUE;
        int aa;
        int bb;
        int cc;
        for (int i=0; i<childList[num].size(); i++){
            if (isCalc[childList[num][i]]==0){
                calc(childList[num][i]);
                isCalc[childList[num][i]]=1;
            }
        }
        
        for (int i=0; i<childList[num].size(); i++){
            aa = myNumUse[childList[num][i]];
            bb = myNumNotUse[childList[num][i]];
            if (aa-bb<myNotUseValue){
                myNotUseValue=aa-bb;
            }
            if (aa>bb){
                myUse += bb;
            }else{
                myUse += aa;
            }
        }
        if (myNotUseValue<=0){
            myNotUse=myUse-sales[num-1];
        }else{
            myNotUse=myUse-sales[num-1]+myNotUseValue;
        }
        myNumUse[num]=myUse;
        myNumNotUse[num]=myNotUse;
        return;
    }else{
        myNumUse[num]=sales[num-1]; //무조건 사용이 최소값이라 생각.
        return;
    }
}


int solution(vector<int> sales1, vector<vector<int>> links) {
    int links_num = links.size();
    for (int i=0; i<sales1.size(); i++){
        sales[i]=sales1[i];
    }
    for (int i=0; i<links_num; i++){
        int a = links[i][0];
        int b = links[i][1];
        childList[a].push_back(b);
    }
    
    calc(1);
    int ans1 = myNumUse[1];
    int ans2 = myNumNotUse[1];
    if (ans1<ans2){
        return ans1;
    }else{
        return ans2;
    }
}

 

---

 

 

처음에 정답은 맞는데 자꾸 시간초과가 됐다.

아무리 생각해도 크게 최적화 해서 이득을 볼 수 있는 부분이 없었는데, 시간초과가 걸려서 고민을 많이 했다...

 

알고보니 전역으로 벡터값을 선언하기 귀찮아서 함수의 인자로 계속 sales라는 벡터를 전달하고 있었는데, 변수의 전달과정에서 복사가 되면서 시간이 엄청나게 늘어나버렸던 것이었다... ㅠㅠ

 

 

[반복되는 부분은 전역으로 선언해 괜한 낭비를 방지하자!]

 

 

프로그래머스