[2021 KAKAO Blind Recruitment] Q7. 매출 하락 최소화 (C++, Python, Java)

문제 링크

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

 

예상 난이도

G2

 

알고리즘 분류

트리 DP

 

풀이

Tree DP를 몰랐으면 절대 풀 수 없습니다. 다만 Tree DP를 알았으면 구현은 쉬운편이었습니다.

 

테이블의 정의는 위와 같습니다.

 

그러면 D[i][0]은 쉽게 식이 도출됩니다.

 

D[i][1]이 살짝 문제인데, 이 경우에는 자식 중에 누군가는 워크숍에 참석하는게 강제되기 때문에 참석했을 때의 손해가 가장 작은 사람이 참석하면 됩니다.

 

만약 D[c][0] - D[c][1]이 모두 음수인 자식이 있다면, 그쪽에서는 애초에 워크숍에 참석하는게 이득인 경우이니 D[c][0] - D[c][1]을 더하는게 아니라 그냥 0을 더해야 합니다. 이게 0과의 max를 계산하는 이유입니다. 이후 테이블을 채워나가면 O(N)에 풀 수 있습니다.

 

코드(C++)

 

코드(Python)

트리가 일자로 생겨있을 경우 재귀 깊이가 최대 30만이고 파이썬에서는 별도로 명령을 하지 않으면 최대 재귀 깊이가 1000이기 때문에 런타임 에러가 발생합니다. 그런 데이터가 없는지 sys.setrecursionlimit 명령을 빼도 통과가 가능했지만 저 명령을 넣어 최대 재귀 깊이를 100만으로 늘리는게 바람직합니다.

 

코드(Java)

 

관련 강의

0x10강 - 다이나믹 프로그래밍

0x19강 - 트리

(제 강의에서 트리 DP는 다루지 않습니다.)