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

본문 링크

import sys
input=sys.stdin.readline

N,K=map(int,input().split())

L=list(map(int,input().split()))

start=0 ; end=sum(L)

while start<=end:
    mid=(start+end)//2 ; count=0 ; total=0
    for i in range(N):
        if total+L[i]<mid:
            total+=L[i]
        elif total+L[i]>=mid:
            count+=1
            total=0
    if count>=K:
        start=mid+1
    else:
        end=mid-1

print(end)

📌 어떻게 현수가 받을 수 있는 최대 점수를 구할것인가?

문제에서 주어진 변수의 범위는 K , N (1 ≤ K ≤ N ≤ 10^5) 이다. 하지만 이를 완전탐색으로 풀기에는 시간이 너무 오래걸리기 때문에 이분 탐색을 통해 풀이하고자 한다.

📌 어떻게 탐색할것인가?

이분탐색의 mid값을 현수가 받을수 있는 점수로 설정한다.
그리고 리스트의 길이만큼 반복문을 돌려 점수의 총합이 mid보다 커지면 count를 1 증가시킨다. 이후 count가 K보다 크거나 같으면 mid값을 증가시키고 그렇지 않다면 end를 감소시킨다.
전형적인 이분탐색 문제이다.

✅ 코드에서 중요한 부분

• 최대값을 구해야하므로 end값을 출력한다.
• end값은 sum(List)로 설정해준다.