https://www.acmicpc.net/problem/2343

문제 이해

1. N개의 음원을 M개의 덩어리로 구분했을 때 덩어리의 최대 값이 최소가 되는 값을 구하자
2. DFS로 풀 수 있지 않을까 생각. M-1개의 구분선을 차례로 움직여 가며 최댓값을 비교해보자

코드

DFS를 생각했다가 그냥 조합으로 가능한 경우를 모두 만들고 시작하면 되지 않을까란 생각으로 아래와 같이 풀었다. 하지만 바로 시간 초과로 실패!N이 최대 10만이니까... 조합의 최대 경우의 수 M이 50000일 때 100000C50000인가.... 가능할 리가 없었다.

from collections import deque
import sys
import itertools
N, M = map(int, sys.stdin.readline().strip().split())
lecture = list(map(int, sys.stdin.readline().strip().split()))
if M == 1:
    print(sum(lecture))
else:
    line = [i for i in range(N-1)]
    ans = 0
    for tmp in itertools.combinations(line, M-1):
        tmp_max = []
        for idx, l in enumerate(tmp):
            if idx == 0:
                tmp_max.append(sum(lecture[0:l+1]))
            elif idx == M - 2:
                tmp_max.append(sum(lecture[tmp[idx-1]+1:l+1]))
                tmp_max.append(sum(lecture[l+1:]))
            else:
                tmp_max.append(sum(lecture[tmp[idx - 1] + 1:l + 1]))
        if ans == 0:
            ans = max(tmp_max)
        if ans > max(tmp_max):
            ans = max(tmp_max)

    print(ans)

이진탐색으로 풀어야 한다니...

import sys
N, M = map(int, sys.stdin.readline().strip().split())
lecture = list(map(int, sys.stdin.readline().strip().split()))
start = 0
end = 0
for i in lecture:
    if i > start:
        start = i
    end += i

while start <= end:
    mid = (start + end) // 2
    c = 0
    tmp = 0
    tmp_max = 0
    for i in lecture:
        tmp += i
        if tmp > mid:
            c += 1
            tmp = i
    if c != 0:
        c += 1
    if c > M:
        start = mid + 1
    else:
        end = mid - 1

print(start)

리뷰

이진탐색을 어떻게 떠올릴까. GPT의 답

최적화 문제: 문제가 가능한 최소 혹은 최대 값을 찾는 최적화 문제일 때, 이진 탐색을 고려할 수 있습니다.

순차적인 레슨의 배열: 레슨의 순서를 바꾸지 않고 연속적으로 블루레이에 저장해야 한다는 조건은, 가능한 블루레이 크기가 일정 범위 내에서 답이 될 수 있다는 것을 시사합니다. 이는 이진 탐색이 가능한 '정렬된' 상태나 '범위'를 필요로 하는 문제와 유사합니다.

결정 문제로의 전환: 최적화 문제를 "이 크기의 블루레이로 모든 레슨을 저장할 수 있는가?"와 같은 예/아니오로 답할 수 있는 결정 문제로 바꿀 수 있습니다. 이진 탐색은 결정 문제를 빠르게 해결하면서 최적의 값을 찾는 데 유용합니다.

범위 내에서의 탐색: 레슨 길이의 최대값과 모든 레슨 길이의 합 사이라는 명확한 범위가 주어졌을 때, 이진 탐색을 사용하여 이 범위를 좁혀나갈 수 있습니다.

탐색 공간의 크기: 레슨 수나 블루레이 크기의 최대값이 충분히 크다면(예: 100,000), 선형 탐색으로는 시간이 너무 오래 걸리므로, 보다 효율적인 탐색 방법인 이진 탐색을 고려해야 합니다.

좀 더 생각해봐야겠다