<알고리즘> Java, 매출 하락 최소화 - Tree(트리), DP

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

프로그래머스

0. 문제 핵심 개념

 

DP(Dynamic Programming) : 동적 계획

DFS(Depth First Search) : stack 활용 끝짱보는 서치

 

단순 완전탐색이 아니라 탐색하면서 중복 계산을 줄여라는 뜻!

= “이미 계산한 결과는 저장해두고 다시 쓰자"

= DFS(자식 먼저 계산) → 그 결과를 이용해 부모 계산

 

 

DFS하면서, 이미 방문한 노드를 다시계산하는걸 방지한다. (시간 아끼려고!)

DFS + Memoization = DFS로 탐색하되 결과를 DP 배열에 저장해둔다.

 

이 문제에서 DP는 아래와 같이 사용한다.

dp[vertex][0] = vertex가 워크샵에 참여하지 않을경우 매출 손실 비용
dp[vertex][1] = vertex가 워크샵에 참여할 경우 매출 손실 비용

 

이때, 팀별로 고려해줘야하므로 가장 최하단의 리프노드부터 진행해주면된다.

---

 

1. vertex(자기자신)이 참석한 경우

 

이를위해 input받은 list배열의 링크를 팀별로 고려해주기위해 정렬했다.

` Arrays.sort(links, a[0]-b[0]);`

 

팀원 각각이 맡고 있는 매출액의 경우의 수 두가지  중 가장 적은 매출액을 맡고 있을 경우를 팀원별로 전부 더해줍니다.

1.  팀원이 참여하지 않은 경우 (not me)
2. 팀원이 참여한 경우 (not me)

즉, 본인제외 모든 팀원들의 합산  `teamSum += min( dp[vertex][0], dp[vertex][1])` 

본인 팀의 모든 팀원에 대해 수행

 

거기에,, `teamSum += sales[me][1]` // 자기자신의 참여값 더해준다.

 

팀장이 팀원들의 매출액의 합산을 넘겨받고, 1번 vertex 까지 넘긴다. (1 == CEO)

`min(DP[1][0], DP[1][1]) + sales[me][1] `이 최종 값이된다. 

---

 

정리! :

`DP[me][1] = sales[x] + sum(min(DP[child][0], DP[child][1]))`

(자식 vertex들의 cost 최솟값 + 자기자신)

• 내가 참석하면
• 내 팀원들은 참석 여부 무관함. (해도되고 안해도되고) -> 최소비용을 선택해준다!!!!

---

2. vertex(자기 자신)이 참석하지 않은경우

-> 2.1 &2.2 두가지 case 로 나뉜다.

2.1. 팀원 한명이 참석하는 게 더 비용이 적은 경우

팀원 중에 적어도 한명이 워크숍에 참석함.

이 경우는 팀장이 워크샵에 참석하지 않는 경우를 의미함. (왜? 자기자신을 팀장이라고 가정해야함.)

 

위에서는 DP[me][1]을 구했지만, 여기에서는 DP[me][0]을 구한다.

 

 DP[child][1] <= DP[child][0] // 팀원 자신이 참여한경우가 최소 매출액이 존재함.

---

정리! :

`DP[me][0] = sum(min(DP[child][0], DP[child][1]))`

(단,  DP[child][1] <= DP[child][0]이 되는 vertex가 존재하는 경우만)

• 내가 불참
• 내 직속부하(팀원) 최소 1명 이상 반드시 참석

 

---

2.2 팀원 중에서 한 명도 참석하지 않은 경우. (전부 불참하는게 비용 적음)

DP[정점][0]를 구하는 두 번째 경우이다. 그럼 적어도 한명 이상의 자식이 워크숍에 참석해야겠죠?

위에서 DP[child][1] <= DP[child][0] 라는 조건이 붙었었다. 이게 존재하지 않는다는 의미이다.

다만 이 경우에는 팀원들의 최소매출액 계산 시, 전부 다 DP[k][0]이 최소가 되는 값밖에 존재하지 않음.

그럼 조건 위반 🚨

-> 팀원들이 참석하는 경우를 억지로 만들어야함.

 

손해를 최소화해야 하니까.... min( DP[child][1] - DP[child][0] )!

팀장이 참석하지않으면, 팀장이 맡아야하는 매출액 최소값 == min(팀원1,팀원2, ... 팀원n)  이 되어야함

근데 전부다 DP[child][0]의 값에 해당함. 누군가는 DP[child][1]로 만들어줘야한다.

==  -DP[child][0] + DP[child][1] 이 최소가 되는 값을 더해주어야 팀장이 맡을 매출액의 합산이 줄어듦을 알 수 있습니다.

각 팀원에 대해 min( DP[child][1]  - DP[child][0] )을 기존 최소합산값에 더해줌.

 

이 경우, 팀원이 참석X 경우가 항상 최솟값이므로 항상  DP[child][1]  -DP[child][0] > 0이다.

---

 

`DP[me][0] = sum(min(DP[child][0], DP[child][1])) + min(DP[child][1] - DP[k][0])`

팀원들의 vertex인, child에 대해 전부 순회한다. 단, DP[child][1]  -DP[child][0] > 0인 경우만!)

 

---

3. 전체 알고리즘 정리 (DFS + DP)

 

DFS(v) {
	dp[v][1] = sales[v];
    dp[v][0] = 0; 
    temp = Integer.MAX_BALUE;
    flag = false;
    
    for(child : children[v]){ //v의 자식노드들에 대해 진행
    	DFS(child);
        
        dp[v][1] += min(dp[child][0], dp[child][1]); // case 1: 본인참여 + 자식 참여 여부 최솟값
        dp[v][0] += min(dp[child][0], dp[child][1]); // 본인참여x
        
        // case2: 2.1, 본인 불참 + 자식 한명이 참여한다.
        if (dp[child][1] <= dp[child][0]){ 
        	flag = true; //한명이상 참여함.
        }
        
        // 2.2 본인불참 & 팀원 전원 불참이 값쌈. :: 한명을 불참 ->참석
        temp = min(temp, dp[child][1] - dp[child][0]); 
        }
        
    // 2.2 (본인참여X, 팀원 억지로 한명 참여시키기  
	if (flag == false) { //전원 불참
   		dp[v][0] += temp;
    }
}

 

 

자바에서 트리를 만들어보자. List를 활용한다

 

List<Integer>[] children = new ArrayList[n + 1];

 

이 표현방식의 의미 : 배열 안에 List가 들어있다. 대괄호 앞에부분 List<Integer>의 배열이라는 의미!!!

ArrayList타입의 배열을 만든다[n+1]크기의.

children
   |
   |-- [0] -> List<Integer>
   |-- [1] -> List<Integer>
   |-- [2] -> List<Integer>
   |-- [3] -> List<Integer>
   ...

 

주의!

배열은 실제 클래스기준으로 만들어짐 : 제네릭 타입 정보는 런타임에 사라진다. 그래서 컴파일단계에서 넘어가기위해서

제네릭 타입의 배열 생성이 금지된다.

ex)

❌ `List<Integer>[] arr = new ArrayList<Integer>[5];` 이런건 불가능하다.

✅  `List<Integer>[] arr = new ArrayList[5]; `  // 경고는 뜰 수 있음

그냥 ArrayList 배열 생성 <Integer> 안 붙었다. 그래서 허용

 

tree/graph 나올때 많이 사용하는 방식

List<Integer>[] arr = new ArrayList[5];

for (int i = 0; i < 5; i++) {
    arr[i] = new ArrayList<>();
}

---

정답 코드

import java.util.*;

class Solution {
    int[][] dp;
    int[] sales;
    int[][] links;
    List<Integer>[] children;
    public int solution(int[] sales, int[][] links) {
        // cost 저장할 배열
        this.sales = sales;
        dp = new int[sales.length+1][2]; 
        children = new ArrayList[sales.length+1];
        
        for(int i=0; i<= sales.length; i++){
            children[i] = new ArrayList<>(); // 미니 ArrayList들 생성
        }
        
        for(int[] link : links){ //트리구조 연결. 
            int parent = link[0];
            int child = link[1];
            children[parent].add(child);
        }
        
        dfs(1);
        
        return Math.min(dp[1][1], dp[1][0]);
        
    }
    

    public void dfs(int v){
        dp[v][1] = sales[v-1];
        dp[v][0] = 0;
        
        boolean flag = false;
        int temp = Integer.MAX_VALUE;
        
        for(int child : children[v]){
            dfs(child);
            
            int min = Math.min(dp[child][0], dp[child][1]);
            dp[v][1] += min;
            dp[v][0] += min;
            
            if(dp[child][1] <= dp[child][0]){
                flag = true;
            }
            temp = Math.min(temp, dp[child][1] - dp[child][0]);  
        }
        if(!flag && children[v].size() > 0){
            dp[v][0] += temp;
        }
    }
}