Search

[백준 2343] 기타 레슨

[백준 2343] 기타 레슨

문제 요약

N개의 강의M개의 블루레이에 나눠 담아야 한다.
담을 때는 강의 넘버링 순서를 지켜서!
강의 갯수가 9, 강의 길이가 다음과 같을 경우
array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Python
블루레이 길이가 개당 10분이라고, 1번째 강의와 9번째 강의를 하나의 블루레이에 담으면 안된다. 1~4번 강의(총 10분)을 담고, 5~6번(총 9분) 담고… 이런 식으로 담아야 함.
가능한 블루레이의 최소 크기를 구해야 한다.

알고리즘 : 이진(이분) 탐색

특정한 범위에서 목표값을 찾아가는 문제는, 이진 탐색으로 범위를 절반씩 좁혀가며 찾아가는 것이 시간복잡도가 Olong(N)으로 효율적!

풀이

1.
탐색 범위 설정
start: 가장 긴 강의의 길이
end: 강의의 전체 총 길이
2.
이분 탐색 알고리즘 구현
while문을 사용하여 탐색 범위의 최솟값이 최댓값을 넘지 않는 경우 계속 반복
mid = (start + end) // 2
여기서 mid는 블루레이의 길이
강의 넘버링 순서를 지켜서 블루레이에 담아야 하므로
tempcnt 변수를 사용하여 체크
temp에 번호 순대로 강의 길이를 더하면서, mid를 넘길 경우 cnt += 1
cnt > m: 필요한 블루레이 갯수 > 정해진 블루레이 갯수 → 블루레이 길이가 짧다!
start = mid + 1: 목표값 더 키우기
cnt <= m: 필요한 블루레이 갯수 ≤ 정해진 블루레이 갯수 → 블루레이 길이가 길다!
result = mid: 일단 최종 결과값에 mid를 저장
end = mid - 1: 목표값을 작게하여, 최솟값 계속 찾아가기

풀이 소스 코드

import sys si = sys.stdin.readline n, m = map(int, si().split()) array = list(map(int, si().split())) start = max(array) # 가장 긴 강의 길이 end = sum(array) # 전체 강의 길이 result = end while start <= end: mid = (start + end) // 2 temp = 0 cnt = 1 for i in range(n): temp += array[i] # 블루레이 하나의 길이를 넘는다면 if temp > mid: cnt += 1 temp = array[i] # 필요한 블루레이 갯수가 정해진 갯수보다 큰 경우 if cnt > m: start = mid + 1 # 블루레이 길이를 더 길게 else: result = mid # 결과값을 현재 mid로 갱신 end = mid - 1 # 블루레이 길이를 더 짧게 하여 최단 길이 찾기 print(result)
Python

포인트

탐색 범위를 적절히 설정하고, 강의 넘버링을 지켜가며 블루레이의 최솟값을 찾아가는 것을 이분 탐색 알고리즘으로 어떻게 구현할 것인지가 핵심
기본적인 이분 탐색 문제는 아니기 때문에 처음 풀면 꽤 고민이 필요할 것
두번째 푸는데도 잘 안풀려서 처음 풀이 코드를 참고해야 했다 ㅠ