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

문제 링크

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

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

---

 

코드

n,k = map(int,input().split())
score = list(map(int,input().split()))
start,end = min(score),sum(score)# 받을 수 있는 최저점수, 받을 수 있는 최대점수
result = 0

while start<=end:
    mid = (start+end)//2#받을 수 있는 최대 점수
    partial_sum = 0#그룹별 시험 점수
    group = 0#시험지를 나눌 그룹의 수
    for i in score:
        partial_sum +=i 
        if partial_sum >=mid:#받을 수 있는 최대점수를 넘으면 그룹으로 나눈다.
            partial_sum=0
            group+=1
    if group>=k:#그룹이 k 이상이면 mid를 저장하고 mid를 증가시켜 탐색.
        result = mid
        start = mid+1
    elif group<k:#그룹이 k 미만이면 mid(받을 수 있는 최대점수)를 줄여 그룹을 증가시킨다.
        end = mid-1
print(result)

---

문제 풀이

받을 수 있는 점수의 범위 (start ~ end)

받을 수 있는 최대 점수를 mid로 하여, 시험점수를 더해가다가 mid를 초과하면 그룹으로 나눈다.

그룹이 k개 이상이면 mid를 result에 저장하고 start를 mid+1하여 받을 수 있는 최대 점수를 증가하여 탐색을 진행한다.

그룹이 k개 미만이면 그룹의 수를 증가시켜야 하므로 end를 mid-1하여 받을 수 있는 최대 점수를 줄이고 탐색을 진행한다.