[백준] 기타 레슨

출처:: www.acmicpc.net/problem/2343

분류:: 이진탐색

 

1. 문제 이해 및 해결과정

- 블루레이에 들어갈 수 있는 최대 시간을 기준으로 이분탐색 - left 는 트랙에서 제일 긴 값 -> max(arr) - right 는 트랙을 전체 합친 값  -> sum(arr)

2. 풀이방법

  1. python

#기타 레슨
#https://www.acmicpc.net/problem/2343
import sys
sys.stdin = open("input.txt","r")
n,m=map(int,input().split())
arr=list(map(int,input().split()))
#이분탐색의 기준은 기타레슨시간의 합(블루레이의 크기)
left=max(arr)
right=sum(arr)
while left<=right:
    mid=(left+right)//2
    sum=0
    cnt=1 #블루레이의 개수
    for x in arr:
        sum+=x
        if sum>mid:
            cnt+=1
            sum=x
    if cnt>m: #개수가 더 많으면
        left=mid+1  #시간을 늘린다.
    else: #블루레이 중 최소
        result = mid
        right=mid-1
print(result)

 

3. 오답원인

  1. left를 1로 하면 답이 될 수 없음, 값을 아무리 작게 해도 트랙에서 제일 긴 것보다는 같거나 커야함 

  - 반례 )  

5 2
1 1 1 1 100
#정답은 100, 잘못된 출력 4

#기타 레슨
#https://www.acmicpc.net/problem/2343
import sys
sys.stdin = open("input.txt","r")
n,m=map(int,input().split())
arr=list(map(int,input().split()))
#이분탐색의 기준은 기타레슨시간의 합(블루레이의 크기)
left=1
right=sum(arr)
while left<=right:
    mid=(left+right)//2
    sum=0
    cnt=1 #블루레이의 개수
    for x in arr:
        sum+=x
        if sum>mid:
            cnt+=1
            sum=x
    if cnt>m:
        left=mid+1
    else: #블루레이 중 최소
        result = mid
        right=mid-1
print(result)

4. 알게된 점