[BOJ/백준] 17951 흩날리는 시험지 속에서 내 평점이 느껴진거야

import sys

def input():
    return sys.stdin.readline().rstrip()


def count_group(val):
    k = 0
    temp = 0
    for ind in range(N):
        temp += arr[ind]
        if temp>=val:
            k += 1
            temp = 0
    return k


N,K = map(int,input().split())

arr = list(map(int,input().split())) 


left = 0
right = sum(arr)+1

while left+1<right:
    mid = (left+right)//2
    K_mid = count_group(mid)
    if K_mid >= K:
        left = mid
    else:
        right = mid
print(left)

 원래 잘 못푸는 이분탐색 문제라서 오래걸렸던 문제였다.

 

이 문제에서 구해야할 것은 최소의 최대값이다.

 

즉 여기서 mid의 값이 의미하는 것은 해당 시험 문제지의 최소 점수인것이다.

 

즉 이 최소 점수가 넘어가면, 그룹을 나누는것이다.

 

이렇게 나눈 최소 점수를 기준으로 시험지를 나눴을때의 그룹의 수가  K개 미만이 되면 False K개 이상이 되면 True로 하고

 

우리는 K개 이상의 가장 마지막 값을 구하고 싶은 것이므로, left를 출력해주면 된다.

 

이 문제 덕분에 이분탐색에 대해서 감을 잡게 되었고,

 

찾고 싶은 값이 있을때 어떻게 나눠야할지 대략 감을 잡았다.

 

아직 부족하지만, 어떻게 나눠야할지 알게 되었다.

 

 

https://blog.naver.com/jinhan814/222156334908

이분 탐색, 파라메트릭 서치 안 헷갈리는 TIP

 

https://blog.naver.com/jinhan814/222135038870

[종만북] 이분 탐색의 구현, 정당성 증명(반복문 불변식)

 

https://eine.tistory.com/entry/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89binary-search-%EA%B5%AC%ED%98%84%EC%8B%9C-%EA%B3%A0%EB%A0%A4%ED%95%A0-%EA%B2%83%EB%93%A4

이진 탐색, 이분 탐색(binary search) 구현시 고려할 것들

 

https://blog.naver.com/kks227/220777333252

이분 탐색(Binary Search) (수정 2019-02-15)

 

풀면서 참조한 블로그들이다. 이분탐색에 대해 잘 설명을 해놓은 블로그이니 추천을 드린다.