2021 KAKAO BLIND RECRUITMENT : 매출 하락 최소화

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

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

 

// 코드

import java.util.*;
 
class Solution {
    
    final static int INF = Integer.MAX_VALUE;
    // sales 복사본
    int[] Sales;
    // 인접리스트
    List<List<Integer>> Child = new ArrayList<>();
    // 비용 : [직원의 번호][참석여부] ex) [1][0] : 1번 직원이 참석하지 않았을 경우, [1][1] : 1번 직원이 참석하였을 경우
    int[][] Cost = new int[300000][2];
    
    
    // traversal 정의 : Child에 구현된 인접리스트를 dfs로 탐색하여 dp를 통해 가장 최소의 비용값을 구한다. 
    //                 탐색을 모두 마치면 최소비용은 루트(CEO) Cost(배열)에 들어있게된다.
    public void traversal(int node) {
        
        // 1.말단노드가 아닐 때, 계속 탐색을 하며 최소 비용을 구해나간다.
        // 1-1.부모노드의 참석/불참석 일 때의 비용값
        // ** 반드시 기저조건보다 위에 있어야 말단노드가 비용을 초기화를 완료 후 부모노드로 올라간다. 
        Cost[node][0] = 0; 
        Cost[node][1] = Sales[node];
        
        // 2.기저조건 : 말단노드일 때
        if(Child.get(node).isEmpty()) return;         
        
        // 3-2.본격적으로 인접리스트 탐색을 하며 비용을 구한다.
        int extraCost = INF; // 부모와 자식이 모두 선택 되지 않았을 경우 별도로 최소비용을 추가해주기 위한 변수        
        for(int c : Child.get(node)) {
            
            // 3-2-1.말단노드에 도달할 때까지 쭉 타고 내려간다.
            traversal(c);
            // 3-2-2.자식노드에서 부모노드로 올라가며 최소 비용을 구한다.
            if(Cost[c][0] < Cost[c][1]) { // 3-2-2-1.자식을 선택하지 않았을 경우(즉, 자식노드를 참석시키지 않는게 더 작은 경우)
                // 부모도 선택되지 않았고, 자식도 선택되지 않았을 경우 --> 추가 작업이 필요(extraCost)
                Cost[node][0] += Cost[c][0];
                // 부모는 선택되고, 자식은 선택되지 않았을 경우 --> 부모가 이미 선택이 되었으므로 자식의 선택여부는 큰 영향을 주지 않는다.
                Cost[node][1] += Cost[c][0];
                
                extraCost = Math.min(extraCost, Cost[c][1] - Cost[c][0]);
            } else { // 3-2-2-2.자식을 선택하였을 경우 -> 이미 자식이 선택되었으므로 부모의 선택에 영향을 받지 않는다.
                Cost[node][0] += Cost[c][1];
                Cost[node][1] += Cost[c][1];
                // 0으로 초기화를 해주므로 이런 상황에서는 기존의 값에 아무런 영향을 주지 않게된다.
                extraCost = 0;
            }
             
        }
        // 추가작업이 필요한 케이스(부모, 자식 모두 선택되지 않았을 경우)에 값을 갱신해준다.
        Cost[node][0] += extraCost;        
    }
    
    
    // main 메서드
    public int solution(int[] sales, int[][] links) {
        
        // 0.사용의 편의를 위해 멤버변수로 복사
        Sales = sales;
        
        // 1.links 인접리스트로 만든다.
        // 1-1.인접리스트 초기화 : sales의 길이가 곧 직원의 수이므로 직원의 수만큼 초기화
        for(int i=0; i<sales.length; ++i) Child.add(new ArrayList<>());
        // 1-2.인접리스트 구현 : 직원의 번호가 1부터 시작하지만 sales는 인덱스가 0부터 시작하므로 편의를 위해 미리 1을 빼준값으로 구현한다.
        for(int[] link : links) Child.get(link[0] - 1).add(link[1] - 1);
        
        // 2. 탐색을 시작한다 : 루트(CEO)부터 시작하여 탐색해 나간다.
        traversal(0);
        
        // 3. 루트노드(CEO)에 해당하는 비용인덱스에 최솟값이 들어있다.
        return Math.min(Cost[0][0], Cost[0][1]);
    }
}