99클럽 코테 스터디 4일차 TIL + 이분검색

초코소금빵·2025년 1월 16일

오늘의 문제(2025-01-14)

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

문제 이해

N개의 강의를 M개의 블루레이에 녹화하기 위한 블루레이의 최소의 크기

https://namu.wiki/w/Blu-ray%20Disc
블루레이가 뭔 지 몰라서 찾아본... (긁적)

알고리즘

이분검색
이분검색인 걸 어떻게 알았냐면, 문제 안에 힌트가 있다!
1) 순서가 뒤바뀌는 경우, 강의의 흐름이 끊긴다!
2) 강의의 수가 최대 100,000개고 강의의 길이가 10,000분이면 100,000x10,000 이기 때문에 백퍼 시간초과가 나온다. 그렇기 때문에 이분탐색을 통해 시간복잡도를 줄여줘야 한다.

문제 입력)
9 3 # 강의의 수 / 저장할 블루레이 개수
1 2 3 4 5 6 7 8 9 # 강의의 길이

문제 출력)
17

[ 1 2 3 4 5 6 7 ]

1번 블루레이 : 1 + 2+ 3+ 4+ 5 = 15
2번 블루레이 : 6 + 7 = 13
3번 블루레이 : 8 + 9 = 17

3개의 블루레이에서 나타낼 수 있는 최소 크기는 17이 되어야한다.

문제 접근

문제를 처음 봤을 때, 이분 탐색인 건 알겠는데 어떻게 풀어야하지?
왜냐면, 이전에 풀었던 것은 크기를 알려주고, 최대 또는 최소를 구해라! 였는데
이번에는 반대로 크기는 안알려주고 최대 또는 최소를 구해라! 이기 때문이다.

아 뭔가 잘 하면 풀 수 있을 거 같은데.. 긁적긁적
으어어어엉어어ㅓ

접근 방법

가장 작은 블루레이 크기: max(강의 길이)
가장 큰 블루레이 크기: sum(강의 길이)

왜?
가장 작은 블루레이 크기라고 하면, 왜 array의 max 값일까? 생각을 해봤다.
[ 1 2 3 4 5 6 7 8 9 ] 의 강의 리스트가 있을 때,

블루레이 개수가 9개이면,
[1][2][3][4][5][6][7][8][9] 로 쪼개질 수 있다.
그렇게 되면, 크기 1,2,3...9가 나오는데

다 담으려면, 크기 9가 되어야한다!
배열에서 가장 큰 값이 블루레이의 가장 작은 값이라고 할 수 있다.

가장 큰 블루레이의 크기는 이해하기 쉬웠...(나는 그랬다.)
그냥 가장 큰 거면 모든 시간을 담아야하니까!

이해하기 위한 예시 설명

크기가 14라고 가정하자.
[ 1 2 3 4 ][5 6] [7][8] [9]
실제 담은 블루레이 개수는 5개가 된다.

1) 크기를 줄이면?

크기가 10이라고 가정하자.
[1 2 3 4][5] [6][7] [8][9]
실제 담은 블루레이의 개수는 6개가 된다.

2) 크기를 늘리면?

크기가 20이라고 가정하자.
[1 2 3 4 5][6 7] [8 9]
실제 담은 블루레이 개수는 3개가 된다.

결과

블루레이의 크기를 줄이면 블루레이의 개수가 늘어난다!
(한번에 담을 수 있는 양이 적으니까!!)

블루레이의 크기를 늘리면 블루레이 개수가 줄어든다!
(한번에 담을 수 있는 양이 많으니까!!)

코드

위의 내용을 참고해서 코드를 작성해봤다..

n,m = map(int,input().split())
time_list = list(map(int,input().split()))
min_size = max(time_list)
max_size = sum(time_list)
while (min_size <= max_size):
    mid_size = (min_size + max_size)//2
    SUM =0
    cnt = 1 ###
    for time in time_list:
        if SUM + time > mid_size:
            cnt +=1
            SUM = 0
        SUM += time
    if cnt <= m: # 개수가 작으면
    	max_size = mid_size -1
    else:
        min_size = mid_size +1
 print(min_size)