[프로그래머스] 매출 하락 최소화 (2021 KAKAO Blind Recruitment)

문제 링크

programmers.co.kr/learn/courses/30/lessons/72416

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

 

풀이

혼자서 푼 건 아니고 친구(dutchcoffee.tistory.com/)가 핵심 아이디어를 알려주었습니다. 😥

 

각 정점 $n$이 팀장으로 있는 팀을 팀 $n$이라고 합시다.

팀 n에서 적어도 한 명이 참석한다는 조건을 만족시킬 때, 팀장이 참석하는 경우와, 팀장이 참석하지 않는 경우의 최솟값을 구해주면 됩니다. 이 값을 $d[n][0], d[n][1]$에 각각 저장합니다.

 

1) 팀 $n$에서 팀장이 참석하는 경우 (line 22 ~ 27)

팀원들의 참석 여부와 상관 없이 팀 $n$은 항상 한 명 이상이 참석한다는 조건을 만족합니다.

따라서 이 경우의 최솟값은 sales$[n]$ + sum( min( $d[i][0], d[i][1]$ ) ), $i =$ ( 적어도 팀원을 한 명 이상 보유한 $n$의 모든 팀원 ) 입니다.

$n$의 팀원 $i$가 팀원을 보유하지 않은 리프 노드라면 굳이 참석하지 않는 것이 최적입니다.

 

2) 팀 n에서 팀장이 참석하지 않는 경우 (line 23 ~ 40)

이 경우엔 팀원 중 적어도 한 명이 무조건 참석해야 합니다. 그럼 여기서 다시 두 가지 경우로 나눠집니다.

 

2-1) 어떤 팀원 $i$가 팀장으로 있는 팀에서 $i$가 참석할 때 더 이득인 경우

어떤 경우에서든 리프 노드는 최대한 참석하지 않아야 최솟값에 가까워집니다.

따라서 리프 노드가 아닌 $n$의 모든 팀원 $i$에 대해, ( $d[i][0] \leq d[i][1]$ )를 만족하는 $i$가 적어도 하나 이상 있다면, 그 팀원들을 참석시키면 됩니다.

그 $i$는 참석하지 않는 것보다 참석하는 편이 코스트가 더 낮아지고, 팀 $n$과 팀 $i$에서 동시에 조건을 만족시키면서 코스트를 가장 적게 가져갈 수 있는 방법이라는 뜻입니다. (line 23 ~ 32)

 

2-2) 모든 팀원이 참석하지 않는 경우가 더 이득인 경우

만약 모든 팀원이 참석하지 않는 경우의 코스트가 더 이득이라면 어쩔 수 없이 한 명을 참석시켜야 합니다. (line 33 ~ 40)

리프 노드가 아닌 각 팀원이 참석할 때의 손해( $d[i][0] - d[i][1]$ ), 리프 노드인 팀원이 참석할 때의 손해( $d[i][0]$ )를 모두 비교해보고 가장 손해가 적은 팀원을 참석시키면 됩니다.

 

정답 코드

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3fLL
#define ft first
#define sd second
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;

ll d[333'333][2];
vvi p;
void go(const vi &cost, int now){
	if(p[now].empty()){
		d[now][0] = cost[now];
		return;
	}
	for(int next: p[now]){
   		go(cost, next);
	}
	d[now][0] = cost[now];
	d[now][1] = 0;
	ll c = false;
	for(int next: p[now]){
		if(!p[next].empty()){
			d[now][0] += min(d[next][0], d[next][1]);
			d[now][1] += min(d[next][0], d[next][1]);
			c |= d[next][0] <= d[next][1];
		}
	}
	if(c) return;
	c = INF;
	for(int next: p[now]){
		if(p[next].empty()){
			d[next][1] = 0;
		}
	   	c = min(c, d[next][0]-d[next][1]);
	}
	d[now][1] += c;
}

int solution(vector<int> sales, vector<vector<int>> links) {
	sales.insert(sales.begin(), 0);
	p.resize(sales.size() + 1);
	for(auto e: links){
   		p[e[0]].push_back(e[1]);
	}
	fill(&d[0][0], &d[0][0]+333'333*2, INF);
	go(sales, 1);
	
	return min(d[1][0], d[1][1]);
}