코드

n, m = map(int, input().split())
arr = list(map(int, input().split()))

# 블루레이 최소 크기
# => 강의 길이 중 가장 큰 값은 담을 수 있어야 함
# => 따라서 가장 긴 강의 시간이 곧 블루레이 최소 크기가 됨
start = max(arr)

# 블루레이 최대 크기
# => 모든 강의를 다 담을 수 있는 경우가 곧 최대
end = sum(arr)

# 로직 구현
def solution(start, end):
    
    # 최종 정답을 담을 변수
    # 블루레이 최소 크기를 구하므로
    # answer는 최대로 잡음
    answer = float('inf')
    
    # 이분 탐색 수행
    while start <= end:
        
        # mid : 블루레이 크기
        mid = (start + end) // 2
        
        # 블루레이 개수
        cnt = 0
        
        # 블루레이 부분합
        _sum = 0
    
        # 블루레이 개수만큼 반복 실시
        for i in range(len(arr)):
            
            # 부분합과 다음 강의의 합이 목표값보다 커지면
            # 목표한 블루레이 크기를 맞췄음
            # cnt의 개수 1 증가
            # 부분합 초기화
            if _sum + arr[i] > mid:
                cnt += 1
                _sum = 0
                
            # 부분합에 각 강의를 더함
            _sum += arr[i]
        
        # 반복문을 다 돌고도 부분합이 남이 있다면
        # 블루레이를 하나 더 써야함
        # 따라서 cnt값 1 증가
        if _sum:
            cnt += 1
            
        # m보다 cnt가 크면
        # cnt의 개수를 줄여야 하므로
        # start + 1
        if cnt > m:
            start = mid + 1
            
        # m보다 크지 않으면
        # answer와 mid 중 더 작은 값을 answer에 대입
        # end = mid - 1
        else:
            answer = min(answer, mid)
            end = mid - 1
            
    return answer
answer = solution(start, end)

print(answer)

문제 해설

이진 탐색 - 파라메틱 서치 문제.

이진 탐색의 경우, 문제에서 이진 탐색을 수행할 목표가 무엇인지를 파악하는게 가장 중요하다. 이 문제의 경우, 주어지는 강의들을 주어진 블루레이의 개수에 맞게 모두 담을 수 있는 블루레이의 최소 크기를 구하는 문제. 이를 토대로 start와 end를 잡으면 아래와 같다

  • start
    • 주어진 강의 중 가장 긴 강의
    • 이보다 짧은 강의 시간으로 블루레이 크기를 설정하면 더 큰 강의는 담을 수 없게 됨
  • end
    • 주어진 강의 시간의 총합

위 포인트를 잘못 잡아 처음에 start를 강의 중 최단 시간의 강의로 잡아 오답 처리가 됐다. 세부적인 코드는 구글링을 통하여 힌트를 얻어 문제를 풀었다. 주어진 강의 시간들을 반복문을 통해 목표한 블루레이 크기에 맞게 부분합을 구하는 방식으로 파라메틱 서치를 적용하면 문제를 해결할 수 있다.

요즘 부쩍 이진 탐색이 매우 어렵게 느껴진다… ㅠㅠ 아무래도 기본 이진 탐색에 조건들이 붙는 경우가 많다 보니 순수한 알고리즘을 사용하는 것이 아니라 응용을 해야하는 경우가 많아서 그런 것 같다. 하루에 2개 이상 이진 탐색 문제를 꾸준하게 풀어 자신감을 얻도록 해야겠다.

댓글남기기

참고