[JS] 매출하락 최소화 (2021 카카오)

tree + dp로 해결할 수 있는 문제였다.

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/72416

프로그래머스

 

 

 

트리구조와 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))
}