프로그래머스1 [프로그래머스] 매출 하락 최소화 풀이 위 그림처럼 트리 구조의 형태로 이루어진 조직도가 있다. 조직도에서 임의의 노드 \(i\)와 노드 \(i\)의 자식들로 이루어진 서브 트리를 팀이라고 하자. 위의 그림에서 A, B, C, D가 팀이다. 임의의 노드 \(i\)를 팀장, 노드 \(i\)의 자식들을 팀원이라 했을 때 모든 팀에서 최소 한 명 이상 워크숍에 참석하면서, 참석하는 직원들의 하루 평균 매출액의 합을 최소로 하는 것이다. 어떤 부모 노드가 워크숍에 참석할 때 자식 노드들이 워크숍에 참석하지 않는 것이 매출액을 최소로 만들 수 있을까? 답은 아니다. 부모 노드의 평균 매출액보다 자식 노드의 평균 매출액 클 경우 반례가 만들어진다. 아래 그림이 그 반례이다. 부모 노드의 참석 여부와 상관없이 자식 노드가 워크숍에 참석했을 경우와 참.. 2022. 9. 18. 이전 1 다음