백준 2343(기타 레슨) - Python(파이썬) - 이분탐색

2343번: 기타 레슨

문제 접근

조건 : 블루레이를 묶을 때는 같은 블루레이 사이에 다른 블루레이가 들어올 수 없으므로 연속되게 묶어야한다.

ex ] 1번, 3번 같은 블루레이 -> 2번 같은 블루레이

 

① 블루레이의 크기가 15라고 할 경우 강의의 합이 15보다 작거나 같게 묶여야하므로

  1번 블루레이에는 (1,2,3,4,5),

  2번 블루레이에는 ( 6,7 )

  3번 블루레이에는 (8)

  4번 블루레이에는 (9) 

이런식으로 묶이게 된다. 그렇게 되면 블루레이의 개수가 4개이므로 조건 3개보다 크므로 블루레이의 크기는 15보다 커야한다.

1

2

3

4

5

6

7

8

9

② 블루레이의 크기가 27라고 할 경우 27보다 작거나 같게 묶여야하므로

  1번 블루레이에는 (1,2,3,4,5,6),

  2번 블루레이에는 ( 7,8,9 )

이런식으로 묶이게 된다. 이 때는 블루레이의 개수가 2개이므로 조건 3개보다 작으므로 블루레이의 크기는 27보다 작아야한다.

1

2

3

4

5

6

7

8

9

③ 이런식으로 늘리거나 줄이거나 할 때 이분 탐색을 이용하여서 구하다보면 블루레이의 크기가 17이라고 할 경우

  1번 블루레이에는 (1,2,3,4,5),

  2번 블루레이에는 (6,7),

  3번 블루레이에는 (8,9)

이런식으로 묶일 수 있게 되어 블루레이의 개수가 3개이게 되므로 블루레이의 크기의 최솟값은 17(출력값)이 된다.

1

2

3

4

5

6

7

8

9

* 이진탐색 Tip

 - 이진탐색은 조건의 만족 여부 (Yes or No) 에 따라서 탐색 범위를 좁혀서 해결

 ex ] 블루레이의 개수가 3개인가 -> No 일경우 블루레이의 크기를 키우거나 작게 만들면 된다.

 - 큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올리기

---

풀이 방법

① 블루레이의 크기 설정

강의의 길이 중 가장 Max인 값 9보다는 크거나 같아야하며 강의의 길이의 합 45보다는 작거나 같아야한다.

( 강의의 길이 Max(9) <= 블루레이의 크기 <= 강의의 길이의 합(1+2+3+4+5+6+7+8+9=45) )

 

② 블루레이의 크기를 가지고 이분 탐색을 한다. 왼쪽 = 9, 오른쪽 =45 -> 중간값 = (9+45)//2 =27로 설정

이 때 나오는 블루레이의 개수를 세고 나서

-> 블루레이의 개수가 조건(3)보다 크게 나올 경우에는 블루레이의 크기를 높여야하므로 28과 45 사이에 있다는 의미

9

27

28

45

 -> 반면, 블루레이의 개수가 조건(3)보다 작게 나올 경우에는 블루레이의 크기를 작게해야하므로 9와 26 사이에 있다는 의미

9

26

27

45

따라서 블루레이의 개수가 클 경우에는 왼쪽 = 중간값 + 1 , 블루레이의 개수가 작을 경우에는 오른쪽 = 중간값 -1

import sys
n,m=map(int,sys.stdin.readline().split())
array=list(map(int,sys.stdin.readline().split()))
#블루레이의 크기 (강의의 길이 max <=블루레이의 크기 <= 강의의 길이 sum)
left,right=max(array),sum(array)

#이분 탐색 시작 left<=right인 경우
while left<=right:
    #중간값
    mid=(left+right)//2
    #cnt값 1로 초기화
    cnt=1
    sum=0
    for i in range(n):
        #sum+array[i]의 값이 중간값보다 큰 경우
        if sum+array[i]>mid:
            #개수 증가,합 초기화
            cnt+=1
            sum=0
        #sum의 값 증가
        sum+=array[i]

    #블루레이의 개수가 조건보다 작을 경우
    if cnt<=m:
        right=mid-1
    #블루레이의 개수가 조건보다 클 경우
    else:
        left=mid+1

print(left)