백준 6236 용돈관리 (python)

문제URL : https://www.acmicpc.net/problem/6236

 

문제 접근법 : 

인출할 금액 정해놓고 여러날에 사용가능하다면 문제가없지만

돈을 다시집어넣고 그 인출할금액을 하루에 딱한번 꺼내서 사용할수없는것도 생각한다면

그금액은 n일동안 인출금액으로 생각하면 안됩니다.

충분히 크게 잡으면서 최소한으로 해야하니

매개변수 탐색으로 

문제를 해결해야합니다

 

소스코드:

from bisect import bisect_left
n,m=map(int,input().split())
v = [int(input()) for i in range(n)]

l,r =0,int(1e15)
res = int(1e15)
while l<=r:
    mid = (l+r)//2
    cnt = 0
    money = 0
    flag = 1
    for i in range(n):
        if money>=v[i]:
            money-=v[i]
        else:
            money = mid
            cnt+=1
            if money <v[i]:
                flag=0
                break
            money-=v[i]

    if cnt<=m and flag:
        res = min(res,mid)
        r=mid-1
    else:
        l=mid+1
print(res)

 

궁금한점 혹은 모르는점 어떤 질무니든 댓글은 언제나 환영입니다.