23.07.01 파이썬 코딩 퀴즈#260 매출 하락 최소화 (프로그래머스 스쿨)

이번 문제는 매출 하락 최소화 문제이다.

카카오 그룹 채용 관련 문제라는게 문제 설명에서 부터 느껴진다.

먼저 그림을 살펴보면

1. 각 원들은 직원 1명을 의미하며, 두개의 숫자는 (직원번호, 하루평균 매출액)을 의미하게 된다.

2. CEO 를 포함하는 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며, 위 그림에서는 관계도를 화살표로 나타내고 있다. 즉, 화살표가 시작되는 쪽은 팀장, 화살표를 받는 직원은 팀원을 의미한다.

2 -1 1번 직원은 화살표를 받지 않고 주기만 하기 때문에 CEO라 볼 수 있다. 즉, 팀장이다

2-2 7,4,6,8,2 번 직원은 화살표를 주지 않고 받기만 하기 때문에 팀원으로만 존재한다.

2-3 9, 5, 10번 직원은 화살표를 받음과 동시에 주기도 하기 때문에 어느팀의 팀원이자, 각 팀의 팀장이 된다.

3. 따라서 해당 조직도에서 1번, 9번, 5번, 10번이 팀장으로 존재하는 총 4개의 팀이 존재하게 된다.

 

제이지는 자신이 구상한 새로운 사업 아이템을 설명하고자 워크숍을 계획하는데, 모든 직원을 참석 시킬 수는 없어 아래와 같이 참석 인원을 선발 하고자 한다.

1. 모든 팀은 최소 1명 이상의 직원을 워크숍에 참석시켜야 한다.

2. 이 때, 참석하는 직원들의 하루 평균 매출액의 합이 최소가 되어야 한다.

이렇게 선별한 인원들의 하루 평균 매출액의 최소합을 구하는 함수를 작성해야 한다.

각 직원의 하루 평균 매출액을 담은 sales 배열과, 직원들의 관계가 담긴 links 배열이 주어진다.

sales 배열은 순서대로 1번 직원부터의 하루 평균 매출액을 담고 있다.

links 배열은 [a,b] 형식이며 a는 팀장의 직원번호, b는 a팀장의 팀원이다.

직원번호 1번은 CEO로 정해져 있으므로, b는 1이 될 수 없다.

따라서 links 배열로 만들어지는 조직도는 하나의 트리 구조 형태이다.

입출력 예 1번은 설명 그림과 같다.

1번, 7번, 10번 직원을 참석 시키게 되면, 모든 팀 A,B,C,D 에서 인원을 참석 시키게 되고, 이때 하루 평균 매출액의 합은 44가 된다.

입출력 예 2번을 그림으로 표현하면 위와 같고, 2번 직원을 참석시키면, A,B 두 팀에 전달 가능하며 이때 값은 6이다.

입출력 3번은 입출력 2번과 같은 형태에 직원들의 매출액만 바뀐 형태이다.

이 경우에는 2번 직원이 아닌, 5번 4번 직원을 참석시키는 것이 5로 최소값이 된다.

입출력 4번을 그림으로 표현하면 위와 같다. 이 경우 4번, 3번 직원을 보내는것이 최소값이 된다.

 

설명에서 알 수 있듯이 이 문제에서 요구하는 부분은 다음과 같다.

1. 각 직원들을 그룹으로 묶어야 한다.

2. 각 그룹에서 인원을 차출할 때 제일 매출액이 적은 직원을 기준으로 1차 선별한다.

3. 선별된 인원들을 대상으로 중복으로 그룹에 존재하는 부분을 제거하여 최소값을 찾는다.

 

또한 links 배열의 길이가 sales보다 1 작다는 의미는, 한 직원이 두 그룹의 팀원으로 존재할 수 없음을 의미한다.

즉 한 직원이 어떤 그룹의 팀장이 되며 다른 그룹의 팀원으로 존재 할 수 있지만, 절대로 다른 두 그룹의 팀원으로는 존재하지 않는다.

위 조직도를 살펴보자.

 

먼저 A,B 그룹에서는 9번을 뽑느것보단 1번과 7번을 뽑는게 이득이다. (14, 13)

다음 A,C 그룹에서는 A에서는 이미 뽑혔기 때문에 C 그룹의 최소값인 10번이 뽑힌다. (17)

그리고 마지막으로 D그룹에서는 6번이 뽑히게 된다. (10)

이 때 각 사원들의 매출액의 합은 54가 된다.

 

다음 A,C 그룹을 먼저 탐색하게 되면, 5번이 먼저 뽑히게 된다. (19)

그리고 A,B 그룹에서는 이미 A 그룹에서 5번이 뽑혔기에 B그룹의 최소값 7번을 뽑으면 된다(13)

D 역시, 6번을 뽑으면 된다.(10)

이 때 각 사원들의 매출액의 합은 42가 된다.

 

마지막으로 A,D 그룹을 먼저 탐색한다고 보면, 3번이 뽑히게 된다 (15)

그리고 B,C 의 최소값 7번과 10번이 뽑힌다. (13, 17)

이 경우 합은 45가 된다.

 

여기서 한가지 드는 의문은 A 그룹을 탐색할 때, 어떤 하위 그룹과 먼저 비교할 것인가이다.

비교하는 두 그룹의 최소값의 합과, 공통으로 존재하는 사원의 값을 어떻게 비교해야 할까?

1. 두 사원을 뽑는것과 공통된 사원 한명을 뽑는것의 기회비용을 비교한다.

1-1 AB 의 경우 14+13, 28 이므로 기회비용은 -1 이다. (즉, 공통된 사원을 뽑을 필요가 없다)

1-2 AC 의 경우 14+17, 19 이므로 기회비용은 12이다.

1-3 AD 의 경우 14+10, 15 이므로 기회비용은 9이다.

따라서 기회비용이 더 큰 AC를 우선 탐색하는게 유리하다.

 

이제 탐색 방향을 정해야 한다.

입출력 예 1번에서 알 수 있듯이 탐색 방향을 제일 하위에서 부터 진행해야 한다.

그 이유는 만약 A에서 부터 내려오게 되면 반드시 C 그룹의 5번을 선택하고 내려오며, 이 경우 뽑히는 사원들은

5번, 7번, 10번으로 1번을 뽑을때보다 5 증가된 값을 가지게 된다.

 

이제 코드를 작성해 보자.

먼저 전달받은 sales 에 index 0 을 삽입해 주고, graph를 만들어 준다.

그 다음 dp 를 생성해 주는데 이때 dp[i] 는 해당 직원을 뽑는것과 안뽑는것 두 가지 값을 쌍으로 가지게 된다.

dfs() 함수를 정의하고, 제일 마지막 직원까지 도달할 수 있도록 한다.

그리고 마지막에 도착한 직원들의 경우 dp[i][1] 은 모두 0 값을 가진다.

입출력 예 1번을 위 코드로 실행해 보면 처음 A,B는 위와 같은 형태를 띄게 된다.

그리고 9번 사원에서 graph[9]를 실행하게 된다.

dp[9][0] += min(dp[7] 을 실행하면 dp[7]의 최소값은 0 즉, 안뽑는 것이 된다.

그리고 choice_value 를 계산해 보면, 13이 되고,

dp[9][1] 은 현재 dp[9] + 13 - sales[9] 이므로 13 이 되며 최종적으로 dp[9] = [28,13] 이 된다.

다음은 A->C->D 구간을 살펴보자.

D 그룹의 경우 10번 사원을 기준으로 실행된다

이 경우 choice_value = 14가 되며, 따라서 dp[10][1] = 14가 된다.

 

그리고 C로 올라오게 되는데,  4번 사원의 choice_value 는 18이고, 10번 사원의 choice_value 는 3이다.

따라서 C의 팀장 5번은 본인이 참석하게 될 경우 19 + 14 + 0  = 33 값을 가지고, 참석하지 않을 경우, 33 - 19 + 3 = 17 값으 을 가지게 된다

따라서 최종적으로 1번 에 그 값들이 모이게 되는데,

1번 사원이 참석할 경우의 값은 각 하위 팀원들의 최소값 + 1번 사원의 판매액 이므로 

14 + 13 + 17+ 0 = 44 가 된다

9번, 5번, 3번 사원들의 경우 choice_value 는 [15, 19, 15] 가 되며, 이 중 최소값이 15가 된다.

따라서 dp[1][1] = 44 + 15 - 14 = 45 가 된다.

 

해당 코드에서 가장 중요한 부분은 먼저 해당 직원이 참석 여부에 따른 값을 나누고, 가장 구하기 쉬운 해당 직원이 참석하는 경우 그 하위 팀원들 중 가장 최소값들만을 그 상위로 전달하는 것이다.

즉 D 팀은 가장 하위이므로, 팀장 d가 참석할 경우 팀장의 판매액, 참석하지 않을 경우 가장 낮은 직원의 판매액을 가지게 된다.

그리고 그 팀장이 팀원으로 속하는 상위 팀 C로 올라가게 되면, 해당 d의 값은[참석할때 최소값, 참석하지 않을때 최소값] 이므로, 그 위 팀장 c의 값은 c가 참석하는경우+d가 참석하지 않는 경우+다른 팀원이 참석하지 않는 경우가 되고

만약 c가 참석하지 않는다고 생각하면, dp[c][0]에 다른 직원(choice_value)을 팀장대신 넣어주고, 팀장의 값 만큼 빼주면 된다. 여기서 choice_value 는 어떤 직원의 참석 여부의 따른 차이 값의 최소값 이므로, 해당 값만큼 더해주면 해당 그룹에서 최소값을 가진 직원이 참석하게 된다.

 

이 부분을 코드로 작성하는게 제일 까다로웠던것 같다.

이미 구해둔 dp[i][0] 값은 현재 i가 참석하는 경우 + 다른 팀원들이 모두 불참하는 경우(다른 팀원들의 [1] 값) 이다.

그리고 i 가 참석하지 않는 다면 미리 구해둔 dp[i][0] 값에 i가 참석하는 값을 빼주고, 그 자리에 다른 직원의 값을 넣어주면 현재 팀에서 참석해야 하는 최소 사원의 값이 된다.