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

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

 

# 흩날리는 시험지 속에서 내 평점이 느껴진거야
N, K = map(int, input().split())
arr = list(map(int, input().split()))

answer = 0
left, right = 0, int(1e5)*20+1
while left <= right:
    mid = (left+right)//2
    # 그룹 나누기
    group = 0
    score = 0
    for s in arr:
        score += s
        if score >= mid:
            group += 1
            score = 0
    # 다음
    if group >= K:
        answer = mid
        left = mid+1
    else:
        right = mid-1

print(answer)

 

이분탐색
1. 입력을 받는다. 출력은 최대 점수 (left와 right을 얻을 수 있는 점수로 설정)
2. left = 0, right = 최대 시험 점수 + 1 (N은 최대 10^5개, 각 점수는 최대 20점)
3. 이분탐색
    - 점수가 mid 일 경우, 각 그룹의 합이 최소가 mid 점수여야 한다.
    - arr의 앞에서부터 더하면서 mid점수를 넘어서면 group += 1, score = 0, answer = mid
    - group의 개수가 K이상이면 left = mid + 1, 아니면 right = mid - 1
4. answer 출력

 

이분탐색에서는 left와 right을 설정할 때 고민이 된다.

문제의 출력이 left와 right의 범위가 되는 경우가 많다.

이 문제에서는 받을 수 있는 최대 점수의 범위가 left와 right의 범위이다.