2021 KAKAO BLIND RECRUITMENT [매출 하락 최소화] [C++]

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

코딩테스트 연습 - 매출 하락 최소화

---

문제 요약

1. 사원의 하루 평균 매출액이 배열로 주어지고, 회사 조직도가 트리 형태의 배열에 담겨서 주어진다.

2. 팀에서 한 명은 회의에 출석해야 된다고 하였을 때 매출 하락의 최소를 출력한다.

 

---

나의 풀이

입출력 예시 1번

A팀에서 누가 나갈지 결정하는 순간 해당 결정이 아래 B, C, D에서 사원을 선택하는 것에도 영향을 끼친다고 생각하여 완전 탐색이나 그리디같이 생각할 수가 없었다.

하나의 팀 입장에서 관찰을 하면 

• 팀장이 회의에 나간다
• 팀원이 회의에 나간다

두 가지의 경우가 있을 수 있다 

하지만 문제 되는 경우 팀원이면서 다른 팀의 팀장이 되는 경우이다 

팀원이면서 다른 팀의 팀장이 되는 사원을 회의로 보내면 해당 선택이 밑의 팀에게 영향을 미치기 때문에 

트리구조상 (leaf)의 팀부터  [예시 1번 상 B, C, D 팀 같은 경우]

1) 팀장이 회의에 나갈 경우 발생하는 최소 매출 하락 

2) 팀원이 회의에 나갈 경우 발생하는 최소 매출 하락

을 저장시킨 다음에 

 

leaf가 아닌 팀들은 하위 팀들이 저장한 

1) 팀장이 회의에 나갈 경우 발생하는 최소 매출 하락

2) 팀원이 회의에 나갈 경우 발생하는 최소 매출 하락

을 이용하여 leaf가 아닌 팀에서의 발생 비용을 계산한다

 

풀이과정 점화식

한 팀에 대해서 d [K][2]로 int 자료형 2개가 필요하다 

d [K][0]= "K" 팀의 팀장이 회의에 나갔을 경우 발생하는 매출 하락 합계의 최솟값

d [K][1]=  "K" 팀의 팀원이 회의에 나갔을 경우 발생하는 매출 하락 합계의 최솟값

 

편의를 위해 팀이름은 팀장의 직원 번호를 따라간다.

 

만약 i 사원 이 K팀의 팀원들이라고 할 경우

d [K][0] 은  K팀 팀장의 하루 매출액 + sum(min(d [i][0],

팀장이 나갔으므로 K팀의 회의가 해소됨 따라서 하위 팀들이 팀원이 나갔는지 팀장이 나갔는지 최솟값만 더해주면 문제가 해결됨

 

d [K][1] 은  세 가지의 경우로 계산이 된다

 

1.  i팀원들이 모두 다른 팀의 팀장일 경우     
   
2.  i팀원들이 모두 리프 팀원일 경우  (리프 팀원이란 "다른 팀의 팀장이 아닌 팀원"을 뜻함)
3.  i팀원 중의 일부는 다른 팀의 팀장이고 일부는 리프 팀원

 

1) d [i][0]<= 경우 가 한 번이라도 있으면

매출 하락을 최소화시키면서 K팀을 대표로 회의에 나갈 수 있으므로 문제가 없다

d [i][1]인 경우 가 한 번이라도 없으면

누군가는 K팀을 대표로 회의에 나가야 하는데 가장 매출 하락을 최소화시키면서 회의에 나가야 하므로

d [i][1]-d [i][0]가 최소인 값을 더해준 다음에 경신한다

 

2)  하위팀이라는 상하관계가 없으므로 그냥

d [i][0]의 값 중 최소인 값을 경신해주면 된다

 

3) i팀원 중 다른 팀의 팀장인 팀원의 d [i][0]<=d [i][1]인 경우 가 한 번이라도 있으면 sum(min(d [i][0], d [0][1]))을 갱신해준다

매출 하락을 최소화시키면서 K팀을 대표로 회의에 나갈 수 있으므로 문제가 없다

 

 만약 d [i][0]<=d [i][1]인 경우가 한 번도 없었으면

"리프 팀원들 중 가장 작은 매출액"과 "다른 팀의 팀장인 팀원의 d [i][0]-d [i][1] 중 최솟값" 중 작은 값을 더해서 갱신해주면 된다.

누군가는 K팀을 대표로 회의에 나가야 하는데 이득인지 아니면 팀장급 팀원이 나가는 게 이득인지는 따져봐야 된다

   

 

---

코드