기타 레슨 (2343번) - 백준 (BOJ)

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

2343번: 기타 레슨

 

 

백준 - 기타 레슨 (2343번)

 

난이도 : Silver 1

알고리즘&자료구조 : Parametric Search, Binary Search (이진 탐색)

 

 

import sys
input = sys.stdin.readline


if __name__ == '__main__':
    N, M = map(int, input().split())
    size = list(map(int, input().split()))
    s, e = max(size), sum(size)
    while s < e:
        m = (s+e)>>1
        cnt = tv = 0
        for v in size:
            if m < tv + v:
                tv = v
                cnt += 1
            else:
                tv += v
        cnt += 1
        if cnt <= M:
            e = m
        else:
            s = m+1
    print(e)

 

 

Parametric Search를 활용하는 문제이다.

 

 

 

풀이 과정

 

 

ⓐ 최솟값 s를 가장 긴 강의 길이인 max(size)로 두고,

최댓값 e를 전체 강의 길이 합인 sum(size)로 설정한다.

 

 

ⓑ while문으로 s 보다 e 가 클 때까지 반복한다.

 

ⓑ-① s와 e의 중간값 m = (s+e)//2 를 기준으로,

필요한 블루레이 갯수 cnt 를 구한다.

 

ⓑ-② cnt가 M보다 작거나 같으면 s ~ m 으로 범위를 좁히고,

cnt가 M보다 크면 (m+1) ~ e 로 범위를 좁힌다.

 

 

ⓒ e 를 출력한다.