[2021 KAKAO Blind Recruitment] Q7. 매출 하락 최소화 (C++, Python, Java)

문제 링크

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

 

예상 난이도

G2

 

알고리즘 분류

트리 DP

 

풀이

Tree DP를 몰랐으면 절대 풀 수 없습니다. 다만 Tree DP를 알았으면 구현은 쉬운편이었습니다.

 

테이블의 정의는 위와 같습니다.

 

그러면 D[i][0]은 쉽게 식이 도출됩니다.

 

D[i][1]이 살짝 문제인데, 이 경우에는 자식 중에 누군가는 워크숍에 참석하는게 강제되기 때문에 참석했을 때의 손해가 가장 작은 사람이 참석하면 됩니다.

 

만약 D[c][0] - D[c][1]이 모두 음수인 자식이 있다면, 그쪽에서는 애초에 워크숍에 참석하는게 이득인 경우이니 D[c][0] - D[c][1]을 더하는게 아니라 그냥 0을 더해야 합니다. 이게 0과의 max를 계산하는 이유입니다. 이후 테이블을 채워나가면 O(N)에 풀 수 있습니다.

 

코드(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> adj[300005];
vector<int> s;
ll d[300005][2];
ll INF = 0x7fffffff7fffffff;
void dfs(int cur){
    if(adj[cur].empty()){ // leaf일 경우
        d[cur][0] = s[cur];
        d[cur][1] = 0;
        return;
    }
    ll mingap = INF;
    d[cur][0] = s[cur];
    for(auto x : adj[cur]){
        dfs(x);
        d[cur][0] += min(d[x][0],d[x][1]);
        mingap = min(mingap, d[x][0] - d[x][1]);
    }
    if(mingap < 0) mingap = 0;
    d[cur][1] = d[cur][0] + mingap - s[cur];
}

int solution(vector<int> sales, vector<vector<int>> links) {
    s.push_back(0);
    for(auto x : sales) s.push_back(x);
    for(auto x : links)
        adj[x[0]].push_back(x[1]);
    dfs(1);
    return min(d[1][0],d[1][1]);
}

 

코드(Python)

import sys
sys.setrecursionlimit(10**6)

adj = [[] for i in range(300005)]
INF = 0x7fffffff7fffffff
d = [[0]*2 for i in range(300005)]
s = []

def dfs(cur):
    if not adj[cur]:
        d[cur][0], d[cur][1] = s[cur], 0
        return None
    mingap = INF
    d[cur][0] = s[cur]
    for x in adj[cur]:
        dfs(x)
        d[cur][0] += min(d[x])
        mingap = min(mingap, d[x][0] - d[x][1])
    if mingap < 0: mingap = 0
    d[cur][1] = d[cur][0] + mingap - s[cur]
    
def solution(sales, links):
    global s
    s = [0] + sales
    for x in links:
        adj[x[0]].append(x[1])
    dfs(1)
    return min(d[1])

트리가 일자로 생겨있을 경우 재귀 깊이가 최대 30만이고 파이썬에서는 별도로 명령을 하지 않으면 최대 재귀 깊이가 1000이기 때문에 런타임 에러가 발생합니다. 그런 데이터가 없는지 sys.setrecursionlimit 명령을 빼도 통과가 가능했지만 저 명령을 넣어 최대 재귀 깊이를 100만으로 늘리는게 바람직합니다.

 

코드(Java)

import java.util.*;
class Solution {
    static ArrayList<Integer>[] adj = new ArrayList[300005];
    static ArrayList<Integer> s = new ArrayList<Integer>();
    static long INF = 0x7fffffff7fffffffL;
    static long d[][] = new long[300005][2];
    static void dfs(int cur){
        if(adj[cur].isEmpty()){
            d[cur][0] = s.get(cur);
            d[cur][1] = 0;
            return;
        }
        long mingap = INF;
        d[cur][0] = s.get(cur);
        for(Integer x : adj[cur]){
            dfs(x);
            d[cur][0] += Math.min(d[x][0], d[x][1]);
            mingap = Math.min(mingap, d[x][0] - d[x][1]);
        }
        if(mingap < 0) mingap = 0;
        d[cur][1] = d[cur][0] + mingap - s.get(cur);
    }
    public int solution(int[] sales, int[][] links) {
        int n = sales.length;
        for(int i = 1; i <= n; i++) adj[i] = new ArrayList<Integer>();
        s.add(0);
        for(int i = 0; i < n; i++) s.add(sales[i]);
        for(int i = 0; i < n-1; i++)
            adj[links[i][0]].add(links[i][1]);            
        dfs(1);
        return (int)Math.min(d[1][0], d[1][1]);
    }
}

 

관련 강의

0x10강 - 다이나믹 프로그래밍

0x19강 - 트리

(제 강의에서 트리 DP는 다루지 않습니다.)

  Comments
댓글 쓰기