BOJ(백준) 2343[기타 레슨]

안녕하세요! 오늘은 백준 온라인 저지의 문제 번호 2343번을 풀어보겠습니다. 이 문제는 주어진 강의 목록을 M개의 블루레이에 나누어 담을 때, 각 블루레이의 크기가 최소가 되도록 하는 문제입니다. 아래는 문제를 해결하기 위한 접근 방법과 정답 코드입니다.

 

1. 문제 설명

주어진 강의 목록에서 M개의 블루레이에 나누어 담을 때, 각 블루레이의 크기가 최소가 되도록 하는 문제입니다.

 

문제URL : https://www.acmicpc.net/problem/2343

 

2. 접근법

1) 입력받기: 강의 수와 블루레이 수, 각 강의의 길이를 입력받습니다.

2) 이진 탐색 초기화: 최소 블루레이 크기와 최대 블루레이 크기를 설정합니다.

3) 이진 탐색 수행: 중간값을 계산하여 블루레이 크기를 조정합니다.

4) 결과 출력: 가능한 최소 블루레이 크기를 출력합니다.

3. 정답 코드

import sys
input = sys.stdin.readline

# 입력 받기
N, M = map(int, input().split())        # N: 강의 수, M: 블루레이 수
arr = list(map(int, input().split()))   # 각 강의의 길이

# 이진 탐색을 위한 초기화
left = max(arr)     # 최소 블루레이 크기는 가장 긴 강의의 길이
right = sum(arr)    # 최대 블루레이 크기는 모든 강의를 하나의 블루레이에 담는 경우
ans = 0             # 가능한 최소 블루레이 크기

# 이진 탐색 시작
while left <= right:
    mid = (left + right) // 2   # 중간값 계산 (현재 블루레이의 크기)
    use = 0                     # 현재 블루레이에 사용된 공간
    cnt = 1                     # 사용된 블루레이 수

    # 각 강의를 블루레이에 담기
    for i in arr:
        use += i
        if use > mid:           # 현재 블루레이에 더 이상 담을 수 없으면
            cnt += 1            # 새로운 블루레이 필요
            use = i             # 현재 강의를 새로운 블루레이에 담기

    # 사용된 블루레이 수가 M보다 많으면 블루레이 크기를 늘려야 함
    if cnt > M:
        left = mid + 1
    else:
        ans = mid           # 현재 블루레이 크기로 가능한 경우 정답 갱신
        right = mid - 1     # 더 작은 블루레이 크기 시도

# 최종적으로 가능한 최소 블루레이 크기 출력
print(ans)

 

4. 코드 설명

이진 탐색 초기화

• left: 최소 블루레이 크기를 가장 긴 강의의 길이로 설정합니다.

• right: 최대 블루레이 크기를 모든 강의를 하나의 블루레이에 담는 경우로 설정합니다.

• ans: 가능한 최소 블루레이 크기를 저장할 변수를 0으로 초기화합니다.

 

이진 탐색 수행

• mid: left와 right의 중간값을 계산하여 현재 블루레이 크기를 결정합니다.

• 각 강의를 순회하면서 현재 블루레이에 담습니다.

• use에 현재 강의를 추가합니다.

• use가 mid보다 커지면 새로운 블루레이가 필요하므로 cnt를 증가시키고, use를 현재 강의 길이로 초기화합니다.

• 사용된 블루레이 수 cnt가 M보다 많으면:

• left를 mid + 1로 조정하여 블루레이 크기를 늘립니다.

• 사용된 블루레이 수 cnt가 M보다 작거나 같으면:

• ans에 현재 블루레이 크기 mid를 저장하고, right를 mid - 1로 조정하여 더 작은 블루레이 크기를 시도합니다.

 

이 코드는 이진 탐색을 통해 효율적으로 블루레이 크기를 찾아내며, 각 강의를 최적으로 분배할 수 있도록 합니다. 이 문제를 해결하는 데 이진 탐색 기법을 사용한 것은 매우 효율적이고 적절한 접근법입니다.

 

5. Github으로 확인

coTest/BOJ/BOJ01_04_05_2343.py at main · pcy4196/coTest