[카카오] 시험장 나누기

문제접근

최대 노드 수: 10000개
그룹을 최대 몇 개까지 나눌 수 있는지: 10000개
완전 탐색 시: 조합(10000!) * 탐색(10000^2)
따라서 각 합에 대한 정보를 memoryzation 해야 하고 검색을 빠르게 해야 한다. 일단 다이내믹 프로그래밍으로 풀어야 할 것 같은 생각이 든다. 합에 대한 정보를 memoryzation 하기에는 너무나 많은 구간과 경의의 수가 있고 모든 합 구간에 대한 memoryzation을 하기 위해선 N^2가 들기에 시간 복잡도가 초과한다. 따라서 조금더 Greedy하게 접근할 필요성을 느낀다. 이분탐색으로 풀기위해서는 합정보에 대한 시뮬레이션 과정을 돌려야 하는데 그과정자체가 N^2이기에 Parametic Search를 해보면 될것같다.
문제를 다음과 같이 변형할 필요가 있다.

처음: K만큼 잘랐을때 그룹의 합들중 최대값이 가장 적은 최솟값을 구한다.
바뀐문제: 그룹의 합의 최대값이 L보다 적거나 같을때 그 횟수가 K보다 작거나 같음을 만족하는 최대 L을 구한다.

풀이

import sys
sys.setrecursionlimit(10 ** 6)
def solution(k, num, links):
    root_candidate = [True for i in range(len(num))]
    dp = [None for i in range(len(num))]
    max_sum = sum(num)
    for a, b in links:
        for i in (a,b):
            if i>=0:
                root_candidate[i] = False
    root = None
    for i in range(len(root_candidate)):
        if root_candidate[i]:
            root = i
            break

    def _travelsal(root, lower_bound):
        left, right = links[root]
        if dp[root] != None:
            return dp[root]
        dp_left, dp_right = [
            _travelsal(i, lower_bound) if i != -1 else [max_sum, 0] for i in [left, right]
        ]
        all_sum = num[root] + dp_left[0] + dp_right[0]
        two_sum = num[root] + min(dp_left[0], dp_right[0])
        if all_sum <= lower_bound:
            dp[root] = all_sum, dp_left[1] + dp_right[1] - 1
        elif two_sum <= lower_bound:
            dp[root] = two_sum, dp_left[1] + dp_right[1]
        else:
            dp[root] = num[root], dp_left[1] + dp_right[1] + 1
        return dp[root]

    left, right = max(num), max_sum
    while left < right:
        dp = [None for _ in range(len(num))]
        mid = (left + right) >> 1
        result = _travelsal(root, mid)
        if result[1] <= k:
            right = mid
        else:
            left = mid + 1
    print(left)
    return left