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

문제

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

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

---

문제 요약

N개의 시험지를 K개의 그룹으로 나눈다.

 

각 그룹에서 맞은 문제 개수의 합을 구하여 그 중 최솟값이 시험 점수가 된다.

 

시험 점수가 최대가 되도록 하는 그룹을 찾고 최대 점수를 출력한다.

 

+ 시험지는 반드시 현재 순서 그대로 그룹으로 나누어야한다. (정렬 X)

---

코드

N, K = map(int, input().split())
# N은 시험지 개수, K는 시험지를 나눌 그룹 수

arr = list(map(int, input().split()))
# 각 시험지마다 맞은 문제 개수

start = 0
end = sum(arr)
# 이진 탐색의 범위 설정

res = 0
# 최대 시험 점수

# start가 end를 넘어갈 때까지 이진 탐색
while start <= end:
    mid = (start + end) // 2
    # mid는 현재 탐색하고 있는 그룹의 최소 점수

    List = [0] * K
    # 각 그룹의 시험 점수 합 저장
    i = 0
    # 그룹 번호
    for num in arr:
        if List[i] > mid:
        # 현재 그룹의 점수 합이 mid 이상이라면 다음 그룹에 저장
           i += 1
        if i == K:
        # 시험지를 나눌 그룹 수를 넘어가면
            break
        List[i] += num
        # i번 그룹에 점수 ++

    res = max(res, min(List))
    # 각 그룹의 시험 점수 중 최솟값 min(List): 현수가 받는 점수
    # 현수가 받을 점수가 이전에 탐색 때 받을 점수보다 크면 갱신

    if min(List) < mid:
    # 각 그룹의 점수 합 중 mid보다 작은 값이 존재한다면
       end = mid - 1
       # mid를 더 작게 검사
    else:
    # 각 그룹의 점수 합이 모두 mid보다 크다면 (조건에 만족했다면)
       start = mid + 1
       # 더 큰 mid값을 탐색 (점수를 더 줄 수있는지)
            
print(res)

---

코드 설명

1. mid 값으로 각 그룹의 최소 시험 점수를 설정하며 이진 탐색을 진행한다.

 

+ List에 각 그룹의 시험 점수 합을 저장한다. (각 그룹의 시험 점수 합은 mid보다 커야한다.)

 

2. 현수가 받을 점수(각 그룹의 시험 점수 중 최솟값)가 이전 탐색 때 저장한 시험 점수보다 크면 갱신한다.

 

3. 각 그룹의 점수가 mid 보다 모두 크다면, 그룹의 최소 시험 점수를 늘려서 점수를 더 줄 수 있는지 탐색한다.

 

3-1. 각 그룹의 점수 중 mid 보다 작은 값이 존재하면, 그룹의 최소 시험 점수를 줄여서 조건에 만족하는 경우가 존재하는지 탐색한다.

 

4. start가 end를 초과하면 이진 탐색을 종료한다.