[Programmers] 매출 하락 최소화

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/72416

프로그래머스

 

트리 DP 알고리즘 문제였고 각 노드에 대해 두 상태를 정의하여 해결할 수 있습니다.

• attendedDp[node]: 노드가 참석했을 때 최소 비용
  • cost = sales[node] + 자식들의 상태와 상관없이 각 자식에 대해 min(attendedDp[child], notAttendedDp[child])의 합

 

• notAttendedDp[node]: 노드가 참석하지 않았을 때 최소 비용
  • 이 경우 node가 팀장이면 반드시 자식 중 한 명 이상은 참석해야 하므로, 기본적으로 자식마다 min(attendedDp[child], notAttendedDp[child])의 합을 구한 뒤 만약 모든 자식이 `참석하지 않음` 상태라면 어떤 한 자식을 참석 상태로 전환하는 추가 비용인 각 자식에 대해 attendedDp[child] - min(attendedDp[child], notAttendedDp[child])을 더해줌

 

처음에는 재귀 형태로 풀어봤으나 N의 최대 크기가 300,000이다 보니 재귀 깊이가 깊어져 stack overflow 에러가 발생해 stack 자료구조를 이용해 DFS를 구현했습니다.

 

 

개발환경: Programmers IDE  

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~