Part3.3_이분탐색(결정알고리즘)&그리디 알고리즘_뮤직비디오(결정 알고리즘)

일단 뇌절이었다.. 뭐지..?
결정 알고리즘 배웠는데 이건... 너무 어렵잖아 ㅋㅋㅋㅋ

문제hint>>
최소 용량은 lt : 1
최대 용량은 rt(한장에 다 담는 것) : 45
mid : 23을 세장에 다 담을 수 있는지 확인한다.

#1. Alt+W+N 입력하고 Alt+W+V :

import sys
sys.stdin = open("input.txt", "rt")

n, m = map(int,input().split())
a = list(map(int,input().split()))
def Count(len):
    cnt=0
    sum=0
    for i in a:
        sum+=i
        if sum > len:
            cnt+=1
            sum=i
    return cnt+1

lt = a[0]
rt = sum(a)
res = 2147000000
while (lt<=rt):
    mid = (lt+rt)//2
    if Count(mid) <= m:
        rt = mid-1
        if res > mid:
            res = mid
    else:
        lt = mid+1
print(res)

100점,....
힌트 보면 할만 한데 이건 내 실력은 아니겠지 ㅎㅎ..

선생님 코드

#1. Alt+W+N 입력하고 Alt+W+V :

import sys
sys.stdin = open("input.txt", "rt")

def Count(capacity):
    cnt=1
    sum=0
    for x in Music:
        if sum + x > capacity:
            cnt+=1
            sum=x
        else:
            sum+=x
    return cnt

n, m = map(int,input().split())
Music = list(map(int,input().split()))

lt = 1
rt = sum(Music)
res = 2147000000

while (lt<=rt):
    mid = (lt+rt)//2
    if Count(mid) <= m:
        res = mid
        rt = mid-1
    else:
        lt = mid+1
print(res)

if res > mid 를 할 필요가 없는게
어차피 저기서 mid는 계속 줄어들고 res 보다 mid가 작아.