매출하락 최소화

출처: https://yabmoons.tistory.com/625 [얍문's Coding World..]

3차for문 지랄지랄 하다가 걍 구글에 검색해서 이분 거 봤다. 개어렵다...

 

다시 직접 코드 쓰면서 이해할라고 적음.

 

DP를 구성 --> 각 인원이, 참가한다? 안 한다? 의 [300000][2]로 배열 만든다.

Min 함수는 더 작은 값 내보내는 함수.

Make_Relation 통해, Node[parent] 벡터에, 그 자식을 넣는다. (팀장이 되는 애의 vector에 팀원 번호 넣기)

 

Cur은, 현재 팀장이 되는 노드다. 해당 Cur : 팀장의 vector size만큼, DFS를 돌린다.

 

이 때, Leaf Node가 참인, 즉 팀원이 없는 애라면, 다시 말해 마지막 노드까지 도달했다면, 

DP[CUR]에서의 최소값은 걔가 참가하거나, 안 하거나다.

따라서

DP[cur][0] == cur이 참가 안한다 == 0

DP[cur][1] == Cost[cur - 1]

return;

 

이렇게 한 팀장의 모든 팀원을 돌았을 땐, 팀장은 3개의 케이스 중 하나를 골라야 한다. 

1) 자기가 참가해야 하는 경우. 이 경우, 팀원이 나가든 말든 일단 신경쓰지 않는다.

2 -1 ) 자기가 참가하지 않고, 팀원을 내보내야 하는 경우 중, 이미 팀원이 나가는 게 이득인 경우

2 -2 ) 자기가 참가하지 않고, 팀원을 내보내야 하는 경우 중, 팀원이 무조건 나가야 하는 경우

 

즉, 만약 CUR이 팀원이자 팀장인 위치일 때, 자기 child 중 팀장인 애가 당첨되었다면? 이건 2-1에 해당한다.

근데, 자기 child 중 팀장인 애가 당첨되지 않은 상황에, 팀장 역시 cost가 크다면? 무조건 child 중 하나를 선택해 내보내야 한다. 이는 2-2에 해당한다.

 

1)은 다음과 같다.

int sum = 0;
for(int i=0; i<Node[cur].size(); i++) {
	int child = Node[cur][i];
	sum += Min(DP[child][0], DP[child][1]);
}
DP[cur][1] = sum + cost[cur-1];

2-1)은 다음과 같다.

int sum = 0;
bool childattend =false;

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]) // 만약 해당 child가 나가는게, 나가지 않는 것보다 낫다면
    	childattend = true;			// cur은 굳이 나가지 않아도 된다.
}

DP[cur][1] = sum + cost[cur-1];

if(childattend = true) 
	DP[cur][0] = sum;

2-2)는

int sum = 0;
bool childattend = false;

//아무도 child중 지원자가 없다면, 아무나 cost가 참가 하는 거랑 참가 안하는 거의 차이가 
//제일 작은 child를 끌고 데려와야 한다.
int Min = 210000000;

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]) // 만약 해당 child가 나가는게, 나가지 않는 것보다 낫다면
    	childattend = true;			// cur은 굳이 나가지 않아도 된다.
    else
    	Min = Min < (DP[cur][1] - DP[cur][0]) ? Min : (DP[cur][1] - DP[cur][0]);
        //그게 아니라면, 참가하는 것 - 참가 안하는 것이 제일 차가 작은 애를
        //억지로 끌고 데리고 나와야됨
}

DP[cur][1] = sum + cost[cur-1];

if(curattend = true) 
	DP[cur][0] = sum;
else
	DP[cur][0] = sum + Min;  //이 경우, 억지로 끌려나온 애(Min) + 그간 더해둔 것(sum)

최종 답은, 사장인 [1]이 [1][0](참가 안하기) 또는 [1][1](참가하기)

#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 leafNode = true;
    
    for(int i=0; i<Node[cur].size(); i++) {
    	int next = Node[cur][i];
        leafNode = false;   
        DFS(next);
    }
    
    if(leafNode) {
        Dp[cur][0] = 0;
        Dp[cur][1] = Cost[cur-1];
        return;
    }
    
    else {
    	int sum = 0;
        int min = 2100000000;
        bool childattend = false;
        
        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]) childattend = true;
            min = min < (DP[child][1] - DP[child][0]) ? 
            	min : (DP[child][1] - DP[child][0]);
        }
        
        DP[cur][1] = sum + Cost[cur];
        if(childattend) DP[cur][1] = sum;
        else DP[cur][1] = sum + min;
    }
}
 
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;
}

 

 

아래는 하다 포기한거

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
vector<pair<int, int>> v;
vector<int> s;

int answer = 0;
int dfs(int head, int min, int headnum) {
    int param;
    //a: head와 맞는 녀석이 있는가?
    //b: 그중 부모노드도 되는 게 있는가?
    //c: 된다면, 자식노드와 비교해서 가장 적은 cost는?
    
    for(int a=0; a<v.size(); a++) {
        //부모노드가 head가 아닌 pair은 pass
        if(head != v[a].first) {
            continue;
        }
        
        for(int b=0; b<v.size(); b++) {
            if(v[a].second == v[b].first) {
                
                //최소값 찾기
                for(int c=0; c<v.size(); c++) {
                    if(v[c].first == v[b].second) {
                        param = s[v[b].first - 1] < s[v[c].first - 1] ? 
                            s[v[b].first - 1] : s[v[c].first - 1];
                    }
                }
                
                answer += dfs(v[a].second, param, s[v[a].second - 1]);
                break;
            }
        }
    }
    int minimum;
    for(int a=0; a<v.size(); a++) {
        if(v[a].first == head)
            minimum = headnum < min + s[v[a].second - 1] ?
            headnum : s[v[a].second - 1];
        else
            continue;
    }
    if(headnum == minimum) {
        return 0;
    }
    else {
        return minimum;
    }
    
}

int solution(vector<int> sales, vector<vector<int>> links) {
    copy(sales.begin(), sales.end(), s.begin() );
    for(int a=0; a<links.size(); a++) {
        v.push_back(make_pair(links[a][0], links[a][1]));
    }
    sort(v.begin(), v.end());
    
    int min = sales[0];
    int headnum;
    for(int a=0; a<links.size(); a++) {
        if(v[a].first == 1) {
            min = min < sales[v[a].second - 1] ? min : sales[v[a].second - 1];
            headnum = sales[0];
        }
        else
            break;
    }
    
    answer += dfs(1, min, headnum);
    return answer;
}