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

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

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

2021 KAKAO BLIND RECRUITMENT의 마지막 문제이다.

알고리즘 분류는 트리에서의 DP 이다.

 

tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설

혼자서 해결하지 못했고 카카오 테크에서 올려놓은 풀이방법으로 코드를 작성하였다.

 

해설

vector<int> adj[MAX];    //인접행렬
int cost[MAX];                 //각 직원의 하루평균 매출액 ex) cost[i]  -  직원번호 i의 하루평균 매출액
int dp[MAX][2];               //dp[i][0] - 해당 직원을 선택하지 않았을 때 최소 가격  dp[i][1] - 해당 직원을 선택했을 때 최소 가격

 

필자는 구현할 때 탑다운 방식을 이용하여 구현했다.

 

이제 점화식을 생각해보자. 총 3가지 경우가 나온다.

 

k가 i의 모든 자식노드라고 할 때

sum_child[i] = ∑ min(dp[k][0], dp[k][1])  

diff = min(dp[k][1] - dp[k][0])

 

1. dp[i][1] =  cost[i] + sum_child[i]

2. dp[i][0] = sum_child[i]

3. dp[i][0] = sum_child[i] + diff

이렇게 3가지의 경우가 나온다.

 

부가 설명을 하자면

1번의 경우는 팀장 노드를 선택하면 하위 자식노드는 최소값만 뽑으면 된다.

 

2번과 3번의 경우는 조금 나누어 주어야 한다. 복잡하다.

-> 만약 i번 팀장노드에서 i번 팀장노드를 선택하지 않았을 때  (dp[i][0]을 채워넣을 때)

-> 자식노드들 중 아무것도 선택이 되지 않았으면 (dp[k][1]을 선택한 경우가 없었으면 여기서 k 는 i의 자식노드)

-> 강제적으로 자식노드들 중에서 하나를 골라주어야 한다.

 

그래서, flag를 활용해서 dp[k][0] > dp[k][1] 이 존재하는 경우

flag = true => 2번 dp[i][0] = sum_child[i]

flag = false => 3번 dp[i][0] = sum_child[i] + diff

 

그리고 자식노드를 순회할 때 diff의 값을 미리 구해놓는데

최소값을 구해놓을 것이므로 diff를 먼저 MAX_INT로 초기화 해놓는다.

k가 i의 자식노드일 때

diff = min(diff, dp[k][1]-dp[k][0]);   으로 저장을 해놓는다.

 

여기서 diff을 왜 dp[k][1]-dp[k][0]의 차로 비교하는지 한참 고민했는데

sum_child[i]에서 dp[k][1]이 선택된 경우가 아얘 없다고 생각하자.

조금더 자세하게 팀장 i도 선택하지 않고 그 하위 자식노드를 하나도 선택하지 않았다고 생각해보자

이 경우 3번의 경우로 강제적으로 하위 자식노드들 중 하나를 선택해준다고 했는데

 

여기서 sum_child[i]는 하위 자식노드를 전부 선택하지 않은것으로 선택되어있다.

하지만 이들 중 하나를 dp[k][0]에서 dp[k][1]로 바꾸게 된다면 

dp[k][0]은 이미 sum_child[i]에 더해져 있으므로 그 차이만큼만 더 더해주면 된다. (dp[k][1]-dp[j][0])

 

마지막으로 해야할 것은 leaf-node로 들어간 경우이다.

이경우는 간단하다.

만약 adj[i].empty() 를 이용해서 인접노드가 비어있으면 cost[i] : 0  선택 했냐 안했냐에 따라서 return 해주면 된다. 

 

이 점화식들을 가지고 top-down dp 를 구현하면 된다.

 

코드