BOJ2343 기타 레슨

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

2343번: 기타 레슨

 

난이도:실버1

소요시간:60분, 반례힌트 사용함

 

아래는 나의 코드인데 구현자체는 빠르게 하였다. 그런데 테스트케이스는 통과를 하는데 채점시 자꾸 틀리는 것이였다. 

반례를 계속 찾아보았지만 찾지못하여 다른사람의 반례를 참고하였다.

그 이유를 찾으니 이분탐색 시작점을 동영상길이의 최대값으로 하였어야 하는데 동영상길이가 디스크보다 클수 없다는 것을 간과하고 min으로 동영상 최솟값으로 설정한게 원인이였다.....  아래로 코드를 수정하니 정답이 나왔다..

    start=max(bluelay_list)

 

이진탐색문제지만 아주 초급단계의 그리디개념도 들어가는 것 같다.

# 9:55 실버1

import sys

N,M =map(int,sys.stdin.readline().split())
bluelay_list=list(map(int,sys.stdin.readline().split()))

def greedy(time,video_list):
    sum=0
    count=1
    for video in video_list:
        if video+sum <=time:
            sum+=video
        else:
            sum=video
            count+=1
    return(count)

def bineary():
    start=min(bluelay_list)
    end=sum(bluelay_list)
    min_time=max(bluelay_list)
    time=end
    while start<=end:
        mid=(start+end)//2
        need_disk= greedy(mid, bluelay_list)
        # print("start: ", start,"end: ", end,"mid: ",mid,"need: ",need_disk)

        if mid<time and mid>=min_time:
            if need_disk<=M:
                time = mid
                end = mid - 1
            else:
                start=mid+1
        else:
            start=mid+1

    return time
print(bineary())