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

문제

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

알고리즘

매개변수탐색

풀이

구간을 나눌 기준을 매개변수로 두고, 그 기준보다 커지면 그룹으로 나누는 방식으로 진행하면 된다.

그룹의 개수가 많다면 기준치를 높여서 줄이는 방향으로, 적다면 기준치를 낮춰서 늘리는 방향으로 진행한다 생각하면 조금 편하다.

코드

inf=10**10

def solve():
    n,k=map(int,input().split())
    arr=list(map(int,input().split()))
    ans=parametric_search(n,k,arr)
    print(ans)

def parametric_search(n,k,arr):
    mn=0
    mx=inf
    ans=0
    while mn<=mx:
        mid=(mn+mx)//2
        cnt,res=check(mid,arr)
        if cnt>=k:
            ans=max(res,ans)
            mn=mid+1
        else:
            mx=mid-1
    return ans

def check(mid,arr):
    nowsum=0
    res=inf
    groupcnt=0
    for i in arr:
        nowsum+=i
        if mid<=nowsum:
            res=min(res,nowsum)
            groupcnt+=1
            nowsum=0
    return groupcnt,res


solve()