[백준/Python] 17951번 : 흩날리는 시험지 속에서 내 평점이 느껴진거야

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

입력

첫 번째 줄에 시험지의 개수 N과 시험지를 나눌 그룹의 수 K가 정수로 주어진다. (1 ≤ K ≤ N ≤ 105)

두 번째 줄에 각 시험지마다 맞은 문제의 개수 x가 정수로 주어진다 (0 ≤ x ≤ 20)

출력

현수가 받을 수 있는 최대 점수를 출력한다.

 

코드

n, k = map(int, input().split())
li = list(map(int, input().split()))

left = min(li)
right = sum(li)
cnt = 0

while left <= right:
    mid = (left + right) // 2
    result = 0
    cnt = 0
    for i in range(n):
        result += li[i]
        if result >= mid:
            cnt += 1
            result = 0
    if cnt >= k:
        left = mid + 1
    else:
        right = mid - 1

print(right)

 

문제풀이

1. 특정 점수를 찾는다는 점으로 이분탐색 접근

2. left를 입력 받은 개수 중 최소값, right를 총 합으로 설정하여 이분탐색 실시

2-1. cnt는 나뉜 그룹(시험지 그룹) 수

3. 특정 mid값에 의해 리스트의 합이 mid값을 넘어가는 순간에 cnt를 1 증가시키고 합을 다시 0으로 초기화 -> 총 나뉘는 그룹 수를 계산

3-1. 나뉜 시험지 그룹이 k보다 크거나 같으면 left를 뒤로 당기기

3-2. 나뉜 시험지 그룹이 k보다 작으면 right를 앞으로 당기기

4. 최종적으로 left가 right를 넘어서는 시점에서 right값을 출력