BOJ 17951 흩날리는 시험지 속에서 내 평점이 느껴진거야

https://www.acmicpc.net/problem/17951
시간 1초, 메모리 256MB
input :

• N K (1 ≤ K ≤ N ≤ 105)
• 맞은 문제의 개수 x(0 <= x <= 20)

output :

• 최대 점수를 출력

조건 :

• K개의 그룹, 맞은 문제 개수의 합을 구하여 그 중 최솟값을 시험 점수

포인터를 사용해야 하나 싶었는데.. 그렇게 따지기엔 너무 경우의 수가 많은 것 같다.
이분 탐색을 이용해 위치를 잡아야 하나 싶었는데 max 값을 따지기도 뭐하고 그룹의 개수가 어떻게 되는지 모르는 상태에서 할 방법이 아니였다.

그래서 분명 이분탐색이긴 한데 무엇을 해야 하는가가 문제였다.
최대 점수를 target으로 하는 이분탐색이고 그룹의 수를 체크한다면? 답을 구할 수 있겠다.

얻을 수 있는 가장 큰 점수는 모든 맞은 문제를 다 더한 값이므로 high 값을 이와 같이 설정 한다.

그리고 mid 점수를 넘은 경우에만 cnt 를 1개 늘려주고 다시 total을 초기화 하도록 하자.
모든 그룹이 최소 점수를 만족 해야 점수를 얻을 수 있으므로 위와 같은 조건이 발생한다.

import sys

n, k = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
low, high = 0, 0

for item in data:
    high += item

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

    cnt, total = 0, 0

    for i in range(len(data)):
        total += data[i]
        
        if total >= mid:
            cnt += 1
            total = 0

    if cnt >= k:
        low = mid + 1
    else:
        high = mid - 1

print(high)