17831번: 대기업 승범이네
첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대
www.acmicpc.net
문제 제목을 봤는데 친구가 사업에 성공했나보다. 속초사는 친구였는데 잘되어서 서울에서 왕부자가 되었다.
이 문제는 2019 홍익대학교 프로그래밍 경진대회 문제였다.
알고리즘 분류 : 트리에서의 다이나믹 프로그래밍.
풀이과정:
dp[MAX][2]를 사용하여
dp[i][0]에는 현 멘토노드를 선택하지 않은경우,
dp[i][1]에는 현 멘토노드를 선택한 경우로 최댓값을 저장하였다.
필자의 경우 현재 보고있는 멘토노드를 기준으로 코드를 작성하였다.
대기업 승범이네의 주인공 승범이가 작성한 코드를 보니 멘티노드 기준으로 작성해도 된다.
점화식은 2개로 나누어진다.
1. dp[i][0] 의 경우 현 멘토노드를 선택하지 않았으므로
i노드의 자식노드를 k라고 할 때 ∑max(dp[k][0],dp[k][1]) 을 더해주고 리턴하면 된다.
2. dp[i][1] 의 경우 현 멘토노드를 선택한 것이므로 멘티 노드들 중 하나만 선택해야한다.
1) i의 모든 자식노드 k에 대해서
dp[k][0] < dp[k][1] 만족하는 모든 dp[k][1]의 값을 더해 놓는다. 이것을 sum_dp_1 이라고하자.
dp[k][0] >= dp[k][1] 만족하는 모든 dp[k][0]의 값을 더해 놓는다. 이것을 sum_dp_0이라고 하자.
두가지 경우를 각각 나눈 이유는 현 멘토노드를 골랐을 때 자식노드가 이미 선택이 되었냐,
선택이 되지 않았냐에 따라 점화식이 달라지기 때문이다.
만약 멘티노드가 선택된경우 = sum_dp_1 + sum_dp_0 - dp[k][1] + cost[curnode] * cost[nextnode] 이고
만약 멘티노드가 선택되지 않은경우 = sum_dp_1 + dum_dp_0 + cost[curnode] * cost[nextnode] 이다.
이를 통해 top_down dp구조로 만들면된다.
그리고 leaf_node일 경우 선택하던 안하던 0을 리턴해준다.
비고 - 다른사람들 코드를 보니 코드를 더 깔끔하게 짤 수 있다. 점화식을 깔끔하게 정리할 수 있다.
코드
'Algorithm' 카테고리의 다른 글
| 백준 - 14442번(벽 부수고 이동하기 2) / C++ (4) | 2021.03.16 |
|---|---|
| 백준 - 14939번(불 끄기) / C++ (0) | 2021.03.12 |
| 프로그래머스 - 매출 하락 최소화 / C++ (2) | 2021.03.08 |
| 프로그래머스 - 합승 택시 요금 / C++ (0) | 2021.03.05 |
| 프로그래머스 - 순위 검색 / C++ (0) | 2021.03.04 |