[JS] 매출하락 최소화 (2021 카카오)
tree + dp로 해결할 수 있는 문제였다.
https://school.programmers.co.kr/learn/courses/30/lessons/72416
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
트리구조와 DP를 활용하면 해결할 수 있는 문제이다.
문제를 처음 읽었을때의 생각은 선택을 했거나, 안했거나를 나누어서 계산을 하는 거였다.
(결과적으로 완전 틀린 접근은 아니었음)
다만 완전탐색으로 이를 해결하기에는 300,000명까지 사원이 있기에 불가능 했다. 주의를 둘 점은 트리구조이기 때문에 1번노드에서 단방향으로 퍼져나가는 구조라고 생각할 수 있다는 것이다.
DP 를
[ 해당 버튼을 누른 경우 최소 매출 , 해당 버튼을 누르지 않은 경우 최소 매출 ]
이라고 생각해보자.
1 ) 뿌리 노드인 경우
뿌리 인 경우 무조건 [ 해당 노드의 매출 , 0 ] 이 되게 된다.
2) 뿌리노드 X
해당 경우는 자식 노드들의 dp값중에서 최솟값들의 합을 취하면된다.
[ 해당노드의 매출 + 자식 노드들의 매출의 최솟값들의 합 , 자식 노드들의 매출의 최솟값들의 합 ]
조금 이상한 부분이 있을 것이다. 문제에서 한 팀에서 1명의 사람은 무조건 뽑아야 한다는 규칙이 있다.
따라서 자식 노드들 중에서 최솟값들을 더했을때 선택이 안된경우, 자식 노드들 중에서 적어도 한개는 선택을 해줘야 한다.
이 때, 선택을 해주었을때의 최솟값이 아닌 증가량을 기준으로 가장 적게 매출이 증가하는 노드를 선택해줘야 한다. 이 경우에는
[ 해당노드의 매출 + 자식 노드들의 매출의 최솟값들의 합 , 자식 노드들의 매출의 최솟값들의 합 + 자식노드를 하나 선택했을때의 증가량 ]
가 된다.
예시를 들어서 보자!
[ , ]
[ , ] [ , ]
[ , ] [ , ]
먼저 DP를 비워주고 뿌리 노드들을 채워보자.
[ , ]
[ , ] [3,0]
[4,0] [5,0]
(2,6) 노드를 채우기 위해서는 먼저 자식 노드의 최솟값들의 합을 봐야한다.
이는 0이다. 즉 [ 6 , a] 까지는 채울 수 있다. a는 2번 노드를 선택하지 않았을때를 가정하는 것이므로 가장 매출 증가량이 적게 되는 5번 노드를 선택한다.
[ , ]
[6,4] [3,0]
[4,0] [5,0]
루트 노드 또한 같은 방식으로 계산해보자.
루트노드를 선택 -> 4 + 0 + 5 = 11
루트노드 선택 X
0 -> 3은 3의 매출이 더 필요하고
4 -> 6은 2의 매출이 더 필요하기에 버튼을 선택한다면 왼쪽 자식을 선택해야 함
[11,6]
[6,4] [3,0]
[4,0] [5,0]
이 되어서 루트노드 2개중 최솟값인 6이 답이 된다.
function solution(sales, links) {
sales = [0,...sales] // 회사원 수 인덱스랑 맞추기
const childs = [...Array(sales.length)].map(_=>[])
for (const [s,e] of links){
childs[s].push(e)
}
//return [parent를 누른 경우, parent를 안누른 경우]
const getPoint = parent => {
if(!childs[parent].length) return [sales[parent],0]
let isSelect = false
let curPoint = 0
// 자식들을 통해 눌러도 되는 point와 아닌 포인트 계산
const childPoints = []
for (const child of childs[parent]){
const [pushPoint,noPushPoint] = getPoint(child)
if(pushPoint <= noPushPoint){
isSelect = true
curPoint += pushPoint
} else {
curPoint += noPushPoint
}
childPoints.push([pushPoint,noPushPoint])
}
// 자식에서 선택이 한명도 안된 경우
if(!isSelect){
let minDiff = Infinity
for (const [pp,npp] of childPoints){
minDiff = Math.min(minDiff,pp-npp)
}
return [sales[parent] + curPoint, curPoint + minDiff]
}
return [sales[parent]+curPoint,curPoint]
}
return Math.min(...getPoint(1))
}