[파이썬/Python] 백준 2343번: 기타 레슨

숨·2024년 8월 15일

📌 문제 탐색하기

N : 강의의 수 $(1 ≤ N ≤ 100,000)$
M : 블루레이의 수 $(1 ≤ M ≤ N)$
N개의 정수 : 각 강의의 길이 $(1 ≤ 정수 ≤ 10,000)$

조건에 맞게 강의들을 M개의 블루레이에 녹화했을 때의 블루레이 크기 중 최소를 구하는 문제이다.

문제 풀이

⭐️ 블루레이 녹화 조건

N개의 강의 순서가 바뀌면 ❌

블루레이의 크기는 최소

M개의 블루레이는 모두 같은 크기

블루레이의 크기가 될 수 있는 범위는 다음과 같다.
1️⃣ 모든 강의가 저장될 수 있어야 함 → 강의 길이 중 최댓값부터
2️⃣ M = 1인 경우 모든 강의가 저장될 수 있어야 함 → 강의 길이의 총합까지

위의 범위 내에서 블루레이 크기를 조절하면서 적절한 값을 찾는다.

⭐️ 적절한 값이란?
전체 강의 길이를 저장한 리스트 요소를 하나씩 접근하면서, 강의가 중간에 끊기지 않도록 블루레이 개수를 센다.
이 개수가 M을 만족했을 때 적절한 값이라 할 수 있다.

이를 이분탐색을 통해 찾아본다.

가능한 시간복잡도

while문으로 min(강의 길이)부터 sum(강의 길이) 사이에서 이분탐색 → $O(log(sum(강의 길이) - min(강의 길이))) = O(log(sum(강의 길이))$
for문으로 이용된 블루레이 개수 세기 → $O(N)$

최종 시간복잡도
총 $O(N * log(sum(강의 길이))$ 이 된다.
최악의 경우 $O(10^5 * log(10^4 * 10^5)) = O(3,000,000)$ 이 되는데
이는 2초 내에 연산이 가능하다.

알고리즘 선택

이분 탐색 구현

1️⃣ 시작값을 min(강의 길이), 마지막값을 sum(강의 길이)로 지정하고 중앙값을 현재 블루레이 크기로 정의한다.
2️⃣ 시작값이 마지막값과 같아지거나 더 작아질 때까지 탐색을 지속한다.
3️⃣ 현재 사용한 블루레이 개수, 블루레이에 담긴 강의 길이를 저장할 변수를 정의한다.
4️⃣ 강의 길이의 누적합을 계산하면서 현재 블루레이 크기로 몇 개의 블루레이를 사용하는지 계산한다.
5️⃣ 블루레이 개수 > M라면? → 시작값을 mid+1로 변경한다.
6️⃣ 블루레이 개수 < M``라면? → 현재 값을 최소 블루레이 크기로 갱신하고 마지막값을 mid-1`로 변경한다.
7️⃣ 이분 탐색이 종료될 때까지 탐색을 지속한다.

📌 코드 설계하기

N, M 입력
강의 길이 입력
이분 탐색 초기값 정의
이분 탐색 수행
결과 출력

📌 시도 회차 수정 사항

1회차

📌 정답 코드

import sys

input = sys.stdin.readline

# N, M 입력
N, M = map(int, input().split())

# 강의 길이 입력
lectures = list(map(int, input().split()))

# 이분 탐색 초기값 정의
start = max(lectures)
end = sum(lectures)
answer = 0

# 이분 탐색 수행
while start <= end:
    # 중앙값 정의
    mid = (start + end) // 2
    # 블루레이 개수 변수 정의
    count = 1
    # 지금 블루레이에 담긴 강의 길이 합
    lectures_sum = 0
    # 블루레이 개수 세기
    for lecture in lectures:
        # 현재 블루레이에 담을 수 있다면 담기
        if lectures_sum + lecture <= mid:
            lectures_sum += lecture
        # 담을 수 없다면 다음 블루레이에 넣기
        else:
            count += 1
            lectures_sum = lecture

    # 블루레이 크기가 적절한 값인지 확인
    if count > M:
        # 블루레이가 더 많이 필요하니까 블루레이 크기 증가
        start = mid + 1
    else:
        # 블루레이 크기가 M 이내면 블루레이 크기 저장하고 크기 감소
        answer = mid
        end = mid - 1

print(answer)