programmers.co.kr/learn/courses/30/lessons/72416
2021 KAKAO BLIND RECRUITMENT의 마지막 문제이다.
알고리즘 분류는 트리에서의 DP 이다.
tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/
혼자서 해결하지 못했고 카카오 테크에서 올려놓은 풀이방법으로 코드를 작성하였다.
해설
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 를 구현하면 된다.
코드
'Algorithm' 카테고리의 다른 글
백준 - 14939번(불 끄기) / C++ (0) | 2021.03.12 |
---|---|
백준 - 17831번(머기업 승범이네) / C++ (0) | 2021.03.10 |
프로그래머스 - 합승 택시 요금 / C++ (0) | 2021.03.05 |
프로그래머스 - 순위 검색 / C++ (0) | 2021.03.04 |
프로그래머스 - 신규 아이디 추천 / C++ (0) | 2021.03.03 |