백준 17951 - 흩날리는 시험지 속에서 내 평점이 느껴진거야 (파이썬)

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

풀이

이분 탐색을 활용해서 시험지 점수 리스트 A를 K개의 그룹으로 나눌 때, 각 그룹의 최소 점수 합 중 최대값을 찾는 문제이다.

문제를 이해하면,

1. N개의 시험지 점수가 주어진다.
2. 이 점수들은 연속된 그룹으로 K개 이상으로 나눠야한다.
3. 그룹의 최소 점수 합이 최대한 커지도록 만든다.

일반적인 풀이로는 시간이 많이 걸리므로, 이분 탐색을 활용해 효율적으로 풀이한다.

1. 이분 탐색 대상
   1. mid 값은 각 그룹의 최소 점수 합 중 최댓값을 의미한다.
   2. low = 0, high = 20 * 100000 / 시험지 개수 최대값이 10^5이므로, 가능한 최대 점수로 정의한다.
2. 이분 탐색 과정
   1. mid 값을 기준으로 그룹을 나눈다.
   2. 그룹의 개수가 K이상이면, mid값을 더 크게 설정
   3. 그룹의 개수가 K미만이면, mid값을 더 작게 설정

코드

# # 백준 17951 - 흩날리는 시험지 속에서 내 평점이 느껴진거야
# 분류 : 이분 탐색

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))

low = 0
high = 20 * 100000
answer = -1

while low <= high :
    mid = (low + high) // 2

    sum = 0
    count = 0
    for i in range(N) :
        sum += A[i]
        if sum >= mid :
            count += 1
            sum = 0
    
    if count >= K :
        answer = mid
        low = mid + 1
    else :
        high = mid - 1

print(answer)