문제

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

카카오 해설

https://tech.kakao.com/2021/07/08/2021-카카오-인턴십-for-tech-developers-코딩-테스트-해설/

아이디어1

파라메트릭 서치

• 범위
  • 최소 : "전체 응시자 수의 합 / k" 와 "가장 많은 응시자 수" 중 큰 값
  • 최대 : "전체 응시자 수의 합"
• 조건
  • 주어진 L에 대해 k개 이하의 그룹으로 모든 그룹의 응시자 수가 L 이하가 되도록 할 수 있는가?

아이디어2

동적 계획법

• dp[i] :
  • i 번 노드 이하의 서브트리가 L 이하의 그룹이 되도록 하는 최솟값

1. 양쪽 자식과 합칠 수 있는 경우
   1-1. 하나 이상의 자식이 없는 경우에도 합칠 수 있다고 침
   1-2. 자식이 없는 경우 자식의 num 은 0
   1-3. dp[i] = num[i] + dp[자식1] + dp[자식2]
   1-4. 그룹 수 유지

2. 한쪽 자식을 끊어내는 경우
   2-1. 둘 중 작은 쪽과 합침
   2-2. dp[i] = num[i] + min(dp[자식1], dp[자식2])
   2-3. 그룹 수 + 1

3. 둘 다 끊어내는 경우
   3-1. dp[i] = num[i]
   3-2. 그룹 수 + 2

< 전체 코드 >

struct node
{
	// 동적 계획법을 통한 파라메트릭 서치 조건 구하기
    int calculate(vector<node>& arr, vector<int>& dp, int L)
    {
        int l_count = 0;
        int r_count = 0;
        int l_value = 0;
        int r_value = 0;
        
        if (m_left != -1)
        {
            l_count = arr[m_left].calculate(arr, dp, L);
            l_value = dp[m_left];
        }
        if (m_right != -1)
        {
            r_count = arr[m_right].calculate(arr, dp, L);
            r_value = dp[m_right];
        }
        
        // count : 그룹 수 - 1
        // root 노드에서 구한 최종 결과에 + 1을 하면 실제 그룹 수를 알 수 있음
        int count = 0;
        if (m_num + l_value + r_value <= L)
        {
            dp[m_ID] = m_num + l_value + r_value;
            return count + l_count + r_count;
        }
        else if (m_num + min(l_value, r_value) <= L)
        {
            dp[m_ID] = m_num + min(l_value, r_value);
            return count + l_count + r_count + 1;
        }
        else
        {
            dp[m_ID] = m_num;
            return count + l_count + r_count + 2;
        }
    }
    
    int m_ID = 0;
    int m_num = 0;
    
    int m_parent = -1;
    int m_left = -1;
    int m_right = -1;
};

int solution(int k, vector<int> num, vector<vector<int>> links) {
    int answer = 0;
    
    vector<node> arr(num.size(), node());
    
    // 매개 변수 정리
    // ID와 응시자 수, 부모, 자식 정보를 가진 노드
    for (int i = 0; i < num.size(); ++i)
    {
        arr[i].m_ID = i;
        arr[i].m_num = num[i];
        
        if (links[i][0] != -1)
        {
            arr[i].m_left = links[i][0];
            arr[arr[i].m_left].m_parent = i;
        }
        if (links[i][1] != -1)
        {
            arr[i].m_right = links[i][1];
            arr[arr[i].m_right].m_parent = i;
        }
    }
    
    // 루트 노드 찾기
    // 파라메트릭 서치 범위 구하기
    node root;
    int sum = 0;
    int m = 0;
    for (auto n : arr)
    {
        sum += n.m_num;
        
        if (m < n.m_num)
            m = n.m_num;
        
        if (n.m_parent == -1)
        {
            root = n;
        }
    }
    
    int low = max(sum / k, m);
    int high = sum;
    
    // 파라메트릭 서치
    while (low < high)
    {
        int mid = (low + high) / 2;
        
        vector<int> dp(num.size(), 0);
        
        if (root.calculate(arr, dp, mid) + 1 <= k)
            high = mid;
        else
            low = mid + 1;
    }
    
    answer = high;
    
    return answer;
}