[ 17951 ] [ 이분 탐색 ] 흩날리는 시험지 속에서 내 평점이 느껴진거야

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

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

 

---

풀이 과정

---

1. 그룹의 맞은 문제의 합의 최솟값을 기준으로 이분탐색을 진행한다.
2. 초기 left를 1, right를 10**5 * 20 + 1로 둔다. 이유는 최소 점수는 1점이고 최대 점수는 그룹이 1개이면서 시험지의 개수가 10**5개이며 각 시험지에서 맞은 문제가 모두 20개일 수 있기 때문이다.
3. 중간값((left + right) // 2)에 대해서 몇개의 그룹이 나오는지 확인한다.
   • 맞은 개수를 더해가면서 중간값보다 커진다면 그룹의 개수를 하나 늘려주고 맞은 개수 초기화
4. 전체 그룹의 개수가 K개보다 많다면 해당 점수로 나눌 수 있는 것이므로 따로 저장 후 오른쪽 구간 진행
5. 전체 그룹의 개수가 K개보다 적다면 해당 점수로 나눌 수 없는 것이므로 왼쪽 구간 진행
6. 따로 저장해둔 정답을 출력시켜 준다. 

---

소스 코드

---

import sys

input = lambda: sys.stdin.readline().rstrip()
N, K = map(int, input().split())
paper = list(map(int, input().split()))

left = 1
right = (10 ** 5 * 20) + 1

answer = 0
while left <= right:
    mid = (left + right) // 2
    group_count = 0
    score = 0
    for p in paper:
        score += p
        if score >= mid:
            group_count += 1
            score = 0

    if group_count < K:
        right = mid - 1
    else:
        answer = mid
        left = mid + 1

print(answer)