99클럽 코테 스터디 4일차 TIL + 백준 2343 기타 레슨 (파이썬)

※ 2343 기타 레슨

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

 

문제 해결 TIP

개인적으로 이분 탐색 알고리즘을 어떻게 적용할지 생각해내기 어려웠던 문제..(문제 이해도 한번에 안되었다.)

그래서 풀이과정을 자세히 써보려 한다.

 

1. 이분탐색의 처음(start)과 끝(end) 구하기

우선 이 문제의 요점은 '블루레이(디스크)의 크기'를 구하는 문제이다. 그렇다면 크기에 초점을 두어 이분 탐색을 적용해보자.

우선 예제에서 강의의 길이가 제일 긴 것은 9분짜리 영상이다. 그렇다면 블루레이(디스크) 용량이 최소한 9분 이상은 저장할 수 있어야 모든 강의를 정상적으로 저장할 수 있을 것이다.

그렇다면 최대는 어떻게 될까? 바로 모든 강의를 하나의 블루레이(디스크)에 저장했을 때이다. 1부터 9까지의 합인 45분이 되어야 할 것이다.

start = max(video)
end = sum(video)

 

2. 블루레이(디스크)의 개수와의 상관관계 이해하기

 

1에서 구한대로 9(start)와 45(end)의 중간인 27로 mid 값을 두어보자. (블루레이의 크기가 27인 경우)

첫 강의부터 최대한 많은 강의를 블루레이(디스크)에 담아보자. 1부터 6까지의 합인 21분짜리 영상을 담을 수 있을 것이다. (7까지 담으면 28분이라 디스크 용량 초과) 따라서 7부터는 새로운 블루레이(디스크) 2에 저장해간다. 7부터 9까지의 영상 총 24분짜리가 담길 것이다.

sum_video = 0 #블루레이에 저장되는 강의 영상 길이의 합
count = 1 #블루레이(디스크) 개수

for i in video:
	if sum_video + i > mid:
		count += 1
        sum_video = 0
    sum_video += i

 

그러나 블루레이 크기가 27인 경우는 블루레이(디스크)의 개수가 2개 나오므로, 문제에서 제시한 M의 값, 3에 맞지 않다. 블루레이(디스크)의 개수를 1개 더 늘려야한다. 그렇다면 블루레이(디스크)의 용량을 줄여야 한다. 45였던 end의 값을 mid - 1인 26으로 두어보자.

9(start)와 26(end)의 중간인 17로 mid 값을 두어보자. (블루레이 크기가 17인 경우)

똑같은 방법으로 진행했다. 3개의 블루레이(디스크)가 생겨났다.

    if count <= M:
        answer = mid
        end = mid - 1
    else:
        start = mid + 1

 

모든 코드를 완성하면 아래와 같다.

 

전체 코드

import sys

N, M = map(int,sys.stdin.readline().split())
video = list(map(int,sys.stdin.readline().split()))

start = max(video)
end = sum(video)

while start <= end:
    count = 1
    sum_video = 0
    mid = (start+end)//2

    for i in video:
        if sum_video + i > mid:
            count += 1
            sum_video = 0
        sum_video += i

    if count <= M:
        answer = mid
        end = mid - 1
    else:
        start = mid + 1

print(answer)

---

• 비기너 문제 : 뜨거운 붕어빵 https://www.acmicpc.net/problem/11945
• 미들러 문제 : 기타 레슨 https://www.acmicpc.net/problem/2343
• 챌린저 문제 : 좋다 https://www.acmicpc.net/problem/1253