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

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

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

[난이도] level4

[유형] DP

[풀이]

sales 배열의 크기가 최대 300000 이므로 판매원을 참석시킬 수 있는 모든 케이스를

다 해보기에는 시간이 너무 오래걸리기 때문에 다이나믹 프로그래밍을 사용해야 합니다.

우선 주어진 입력을 이용해 2차원 tree vector에 tree[parent].push_back(child) 와 같이

트리 형식으로 저장해줍니다.

Top-Down 방식을 이용하였고 sol(n)은 DP[n]은 구하고 return 합니다.

DP 배열은 아래와 같이 간단히 정의합니다.

DP[n] : 루트가 n인 트리의 최소 비용.

루트가 n일때, 루트인 n 혹은 그 자식 노드중에 하나는 회의에 참석해야 합니다.

위의 케이스를 모두 계산해보고 그 중 최솟값을 DP[n]의 값으로 확정짓는 방식으로 DP[n]을 구합니다.

우선 풀이에 사용될 변수 v를 아래와 같이 정의합니다.

v : n의 자식 노드가 nxt일 때 모든 DP[nxt]의 합

v = sum(DP[nxt])

점화식은 아래와 같습니다.

DP[n] =

i) n을 회의에 참석 시킬 때,

n을 참석 시킬 때 비용 sales[n]에 n의 자식 노드들의 최소비용을 더해주기만 하면 되므로

v + sales[n] 이 됩니다.

ii) n의 자식 중 하나인 nxt를 회의에 참석 시킬 때,

root인 n은 참여하지 않았으므로 sales[n]은 더할 필요 없이

일단 v 값에 sales[nxt]를 더해줍니다.

v값은 업데이트 되면 안되므로 임시변수 t를 선언하였습니다.

t = v+sales[nxt]

여기서 v에 더해져 있던 sol(nxt) 값은 nxt가 회의에 참석 되는 것이 확정되었으므로

t에 빼주어야 합니다. 왜냐하면 sol(nxt)에는 nxt가 참여한 경우, 참여하지 않은 경우가 모두

포함되어 있기 때문입니다.

t = v+sales[nxt]-sol(nxt)

여기까지 해주면 nxt의 자식들이 nnxt라고 했을 때, sol(nnxt)의 값도 빠져버려 nxt 자식 트리들의

비용은 반영이 안되어 버리기 때문에 sol(nnxt)의 값들은 다시 더해줘야 합니다.

t = v+sales[nxt]-sol(nxt)+sum(sol(nnxt)) (nnxt는 nxt의 자식노드들)

위의 t 값이 nxt를 회의에 참여 시켰을 때의 최솟값이 됩니다.

만약 sol(n)에서 n의 자식이 없다면 회의에 참석할 필요가 없기 때문에 0을 return 합니다.

최종 DP[n]은 i),ii) 케이스 둘에서 나온 값들 중에 최솟값이 됩니다.

#include #include #include #include using namespace std; vector sales,tree[300001]; int dp[300001],inf=1<<31-1; int sol(int n){ if(tree[n].empty()) return 0; int& ret = dp[n]; if(ret!=-1) return ret; ret=inf; int v=0; for(int nxt : tree[n]) v+=sol(nxt); ret=min(ret,v+sales[n-1]); for(int nxt : tree[n]){ int t = v-sol(nxt); t+=sales[nxt-1]; for(auto nnxt : tree[nxt]) { if(!tree[nnxt].empty()) t+=sol(nnxt); } ret=min(ret,t); } return ret; } int solution(vector _s, vector> links) { sales = _s; memset(dp,-1,sizeof(dp)); for(auto l : links) tree[l[0]].push_back(l[1]); return sol(1); }

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/매출_하락_최소화.cpp

from http://leesh111112.tistory.com/309 by ccl(A) rewrite - 2021-09-04 18:26:43