백준 2343번 기타 레슨 Python

---

백준 2343번 기타 레슨 Python

---

문제설명

🔹 문제

강토는 자신의 기타 강의 영상을 블루레이에 담아 판매하려고 합니다. 총 N개의 강의가 있으며, 이 강의들을 M개의 블루레이에 나눠서 담으려 합니다.

중요 조건은 다음과 같습니다:

• 강의의 순서를 바꿀 수 없습니다. (선형 순서 유지)
• 한 블루레이에는 연속된 강의들만 들어가야 합니다.
• 모든 블루레이는 동일한 크기여야 합니다.
• M개의 블루레이에 모두 담되, 블루레이 크기는 최소가 되도록 해야 합니다.

🔹 입력 형식

• 첫째 줄: `N` (강의 수), `M` (블루레이 수)
  (`1 ≤ N ≤ 100,000`, `1 ≤ M ≤ N`)
• 둘째 줄: 각 강의의 길이 (분 단위, 자연수, 최대 10,000)

🔹 출력 형식

• 가능한 블루레이 크기 중 최소값을 출력합니다.

🔹 테스트케이스

예제 입력 1

9 3
1 2 3 4 5 6 7 8 9

예제 출력 1

17

---

설명

예를 들어 강의 길이가 다음과 같습니다.

1 2 3 4 5 6 7 8 9

총 9개의 강의입니다. 이 강의들을 3개의 블루레이에 나누어 담아야 합니다.

블루레이는 다음과 같은 조건을 가집니다:

• 모든 블루레이는 같은 크기여야 합니다.
• 한 블루레이에는 연속된 강의들만 들어갈 수 있습니다.
• 강의 순서는 바꿀 수 없습니다.

이 조건을 만족하면서, 각 블루레이의 용량(최대 담을 수 있는 총합)을 가능한 한 작게 만들어야 합니다.

예를 들어, 블루레이 크기를 17로 정하면 다음과 같이 나눌 수 있습니다.

[1 2 3 4 5 2] → 합: 17 이하  
[6 7]         → 합: 13  
[8 9]         → 합: 17

총 3개의 블루레이에 담을 수 있고, 각 블루레이 크기가 모두 17 이하이므로 조건을 만족합니다.

이보다 더 작은 크기로도 3개에 담을 수 있는지 확인하며, 가능한 블루레이 크기 중 가장 작은 값을 찾아야 합니다.

---

아이디어

이분탐색의 전제조건: 정렬

• 이분 탐색을 하려면 값들이 정렬된 상태여야 합니다.
• 예를 들면 다음과 같이 정렬된 수가 있다고 가정합니다.

1, 2, 3, 4, 5, 6, 7

• 이 배열에서 찾고자 하는 값이 3이라고 가정합니다.
• 이때 중간값은 4입니다.

1, 2, 3, {4}, 5, 6, 7

• 우리가 찾는 값인 3은 중간값 4보다 작기 때문에
• 이제 탐색 범위는 다음과 같이 줄어듭니다.

1, 2, 3

• 여기서 다시 중간값은 2입니다.

1, {2}, 3

• 찾고자 하는 값 3은 2보다 크므로
• 이제 탐색 범위는 다음과 같이 줄어듭니다.

3

• 이처럼 이분 탐색은 항상 정렬된 배열에서 중간값을 기준으로 직접적인 수치를 기반으로 탐색 범위를 줄여가며 찾고자 하는 값을 좁혀가는 방식입니다.
• 따라서 이 문제에서도 가능한 블루레이 크기들을 정렬된 수의 집합으로 생각할 수 있으므로 이분 탐색이 가능합니다.

---

이진 탐색 진행 과정

현재 탐색 배열입니다.

9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45

• 시작값은 9입니다.
• 끝값은 45입니다.
• 중간값은 (9 + 45) / 2 = 27입니다.

9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, {27}, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45

블루레이 용량을 27로 설정합니다. 강의 배열은 다음과 같습니다.

1, 2, 3, 4, 5, 6, 7, 8, 9

1부터 누적합을 구합니다.

• 1 + 2 = 3
• 3 + 3 = 6
• 6 + 4 = 10
• 10 + 5 = 15
• 15 + 6 = 21
• 21 + 7 = 28 → 27을 초과하므로 블루레이 1개 완성
  → 첫 번째 블루레이: 1 + 2 + 3 + 4 + 5 + 6 = 21

7부터 다시 시작합니다.

• 7 + 8 = 15
• 15 + 9 = 24 → 가능
  → 두 번째 블루레이: 7 + 8 + 9 = 24

총 블루레이 개수는 2개입니다.

2개는 우리가 사용할 수 있는 최대 블루레이 수인 3개 이하이므로, 27이라는 용량으로 강의를 나눌 수 있습니다. 더 작은 용량으로도 가능할 수 있으므로 탐색 범위를 줄입니다.

---

이제 새로운 탐색 배열은 다음과 같습니다.

9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26

• 시작값은 9입니다.
• 끝값은 26입니다.
• 중간값은 (9 + 26) / 2 = 17입니다.

9, 10, 11, 12, 13, 14, 15, 16, {17}, 18, 19, 20, 21, 22, 23, 24, 25, 26

블루레이 용량을 17로 설정합니다. 강의 배열은 그대로입니다.

1, 2, 3, 4, 5, 6, 7, 8, 9

1부터 누적합을 구합니다.

• 1 + 2 = 3
• 3 + 3 = 6
• 6 + 4 = 10
• 10 + 5 = 15
• 15 + 6 = 21 → 17 초과 → 블루레이 1개 완성
  → 첫 번째 블루레이: 1 + 2 + 3 + 4 + 5 = 15

6부터 다시 시작합니다.

• 6 + 7 = 13
• 13 + 8 = 21 → 17 초과 → 블루레이 2개 완성
  → 두 번째 블루레이: 6 + 7 = 13

8부터 다시 시작합니다.

• 8 + 9 = 17 → 가능
  → 세 번째 블루레이: 8 + 9 = 17

총 블루레이 개수는 3개입니다. 3개는 조건을 만족합니다. 더 작은 용량으로도 가능할 수 있으므로 탐색 범위를 더 줄입니다.

---

현재 탐색 배열입니다.

9, 10, 11, 12, 13, 14, 15, 16

• 시작값은 9입니다.
• 끝값은 16입니다.
• 중간값은 (9 + 16) / 2 = 12입니다.

9, 10, 11, {12}, 13, 14, 15, 16

블루레이 용량을 12로 설정합니다.

강의 배열은 다음과 같습니다.

1, 2, 3, 4, 5, 6, 7, 8, 9

1부터 누적합을 계산합니다.

• 1 + 2 = 3
• 3 + 3 = 6
• 6 + 4 = 10
• 10 + 5 = 15 → 12 초과 → 블루레이 1개 완성
  → 첫 번째 블루레이: 1 + 2 + 3 + 4 = 10

5부터 다시 시작합니다.

• 5 + 6 = 11
• 11 + 7 = 18 → 12 초과 → 블루레이 2개 완성
  → 두 번째 블루레이: 5 + 6 = 11

7부터 다시 시작합니다.

• 7 + 8 = 15 → 12 초과 → 블루레이 3개 완성
  → 세 번째 블루레이: 7

8부터 다시 시작합니다.

• 8 + 9 = 17 → 12 초과 → 블루레이 4개 완성
  → 네 번째 블루레이: 8

9만 남음
→ 다섯 번째 블루레이: 9

총 블루레이 개수는 5개입니다.

조건은 3개 이하이므로 12는 너무 작습니다.

→ 탐색 범위를 더 큰 값으로 좁혀야 합니다.

---

새로운 탐색 배열은 다음과 같습니다.

13, 14, 15, 16

중간값은 (13 + 16) / 2 = 14입니다.

13, {14}, 15, 16

블루레이 용량을 14로 설정합니다.

강의 배열:

1, 2, 3, 4, 5, 6, 7, 8, 9

누적합 계산:

• 1 + 2 = 3
• 3 + 3 = 6
• 6 + 4 = 10
• 10 + 5 = 15 → 초과 → 블루레이 1
  → 블루레이 1: 1 + 2 + 3 + 4 = 10

5부터:

• 5 + 6 = 11
• 11 + 7 = 18 → 초과 → 블루레이 2
  → 블루레이 2: 5 + 6 = 11

7부터:

• 7 + 8 = 15 → 초과 → 블루레이 3
  → 블루레이 3: 7

8부터:

• 8 + 9 = 17 → 초과 → 블루레이 4
  → 블루레이 4: 8

9만 남음
→ 블루레이 5: 9

총 블루레이 개수는 5개입니다. 조건 초과입니다.

14는 여전히 작습니다. → 탐색 범위를 더 크게 합니다.

---

다음 탐색 배열은:

15, 16

중간값은 (15 + 16) / 2 = 15입니다.

{15}, 16

블루레이 용량을 15로 설정합니다. 계산 반복합니다.

• 블루레이 1: 1 + 2 + 3 + 4 = 10
• 블루레이 2: 5 + 6 = 11
• 블루레이 3: 7 + 8 = 15
• 블루레이 4: 9

총 블루레이 개수: 4
조건 초과 → 15는 부족합니다. → 다음 탐색 배열은

16

중간값 16 → 직접 판단

• 블루레이 1: 1 + 2 + 3 + 4 = 10
• 블루레이 2: 5 + 6 = 11
• 블루레이 3: 7
• 블루레이 4: 8
• 블루레이 5: 9

→ 총 5개 → 초과
→ 16도 불가능

---
다시 이전 단계로 돌아가겠습니다. 이미 17에서는 가능했기 때문에 최소 가능한 값은 17입니다.

최종 정답은 17입니다.

---

left와 right가 역전되는 순간

이전 탐색 흐름은 다음과 같습니다.

• 탐색 배열:

[9, 10, 11, ..., 15, 16, 17, 18, ..., 45]

• 중간값 `mid = 27` → 가능
  → 탐색 범위 줄임: `right = 26`
• `mid = 17` → 가능
  → `right = 16`
• `mid = 12`, `14`, `15`, `16` → 불가능
  → `left = 17`
  → 마지막 상태:

left = 17  
right = 16  

이 시점에서 left > right입니다. 이 순간이 바로 탐색 종료 조건입니다.

---

왜 이 순간 left가 정답인가?

1. right는 실패한 값들의 마지막 지점입니다.

• right가 16이라는 것은, 용량이 16일 때 강의를 3개 이하로 나눌 수 없다는 것을 의미합니다.
• 그보다 작은 값들 (`15, 14, ... 9`)도 모두 실패였습니다.
• 따라서 16 이하는 모두 불가능한 값의 영역입니다.

2. left는 성공했던 영역의 가장 첫 지점입니다.

• left가 17이라는 것은, 용량이 17일 때 강의를 정확히 3개로 나눌 수 있었다는 의미입니다.
• 그보다 큰 값들도 모두 가능하지만, 우리는 가장 작은 가능한 값을 찾고 있기 때문에 이 시점에서 left는 최소 가능한 값입니다.

---

시각화로 정리

탐색 전 배열:

[9, 10, 11, ..., 15, 16, 17, 18, ..., 45]

이진 탐색 후 실패 영역:

❌ 9, 10, 11, 12, 13, 14, 15, 16  

성공 영역:

✅ 17, 18, 19, ..., 45

결정 순간:

left → 17  
right → 16  

→ 역전 발생 → 탐색 종료
→ left = 17이 최소 정답으로 확정됩니다.

---

아이디어 요약

• 이분 탐색에서 `left > right`가 되는 순간은 최소값을 찾는 문제에서의 정답 확정 순간입니다.
• 그 이유는 left는 가능한 영역의 경계선이며, 그 앞은 모두 실패했기 때문입니다.
• 따라서 left는 처음으로 조건을 만족한 값이 되며, 이 값이 바로 우리가 찾는 최소 블루레이 용량입니다.

---

✅ 전체코드

N,M=map(int,input().split())

arr=list(map(int,input().split()))


left = max(arr) # 블루레이 크기의 최소값은 가장 긴 강의 길이
right=sum(arr) # 블루레이 크기의 최대값은 모든 강의 길이의 합
answer=0 # 최종 정답을 저장할 변수

while left<=right: # left가 right보다 작거나 같을 때까지 반복
    mid=(left+right)//2 # 중간값 계산 (현재 블루레이 크기 후보)
    k=1 # 필요한 블루레이 개수 (최소 1개로 시작)
    sum_N=0 # 현재 블루레이에 담긴 강의 길이의 합

    for i in range(N): # 모든 강의를 순회하며 블루레이에 담아봅니다.
        if sum_N+arr[i]<=mid: # 현재 강의를 담아도 mid 크기를 넘지 않으면
            sum_N+=arr[i] # 현재 블루레이에 강의를 추가
        else: # 현재 강의를 담으면 mid 크기를 넘으면
            sum_N=arr[i] # 새 블루레이를 시작하고 현재 강의를 담음
            k+=1 # 필요한 블루레이 개수 증가

    if k<=M: # 현재 mid 크기로 M개 이하의 블루레이에 담을 수 있다면 (조건 만족)
        answer=mid # mid는 가능한 답이므로 저장
        right=mid-1 # 더 작은 크기로도 가능한지 탐색 (최소값을 찾아야 하므로)
    else: # 현재 mid 크기로 M개 초과의 블루레이가 필요하다면 (조건 불만족)
        left=mid+1 # mid는 너무 작으므로 더 큰 크기로 탐색

---

🔍 코드 분해 및 설명

📌 [1] 입력 및 리스트 생성

N,M=map(int,input().split())

arr=list(map(int,input().split()))

• `N`과 `M`은 각각 강의 수와 블루레이 수를 입력받아 정수로 변환합니다.
• `arr`는 각 강의의 길이를 입력받아 정수 리스트로 저장합니다.

📌 [2] 탐색 범위 설정 및 변수 초기화

left = max(arr) # 블루레이 크기의 최소값은 가장 긴 강의 길이
right=sum(arr) # 블루레이 크기의 최대값은 모든 강의 길이의 합
answer=0 # 최종 정답을 저장할 변수

• `left`: 가능한 블루레이 크기의 최솟값입니다. 한 강의는 반드시 하나의 블루레이에 들어가야 하므로, 가장 긴 강의 길이보다는 블루레이 크기가 커야 합니다.
• `right`: 가능한 블루레이 크기의 최댓값입니다. 모든 강의를 하나의 블루레이에 담는 경우이므로, 모든 강의 길이의 합이 됩니다.
• `answer`: 조건을 만족하는 최소 블루레이 크기를 저장할 변수입니다.

📌 [3] 이진 탐색 루프

while left<=right:
    mid=(left+right)//2
    k=1
    sum_N=0

    for i in range(N):
        if sum_N+arr[i]<=mid:
            sum_N+=arr[i]
        else:
            sum_N=arr[i]
            k+=1

    if k<=M:
        answer=mid
        right=mid-1
    else:
        left=mid+1

• `while left <= right`: `left`가 `right`보다 작거나 같을 때까지 반복하여 탐색을 진행합니다. 이 조건은 `left`와 `right`가 같아지는 마지막 경우까지 확인하여 정확한 최솟값을 찾을 수 있도록 합니다.
• `mid = (left + right) // 2`: 현재 탐색 범위의 중간값을 계산하여 블루레이 크기 후보로 사용합니다.
• `k = 1`, `sum_N = 0`: 현재 `mid` 크기로 강의를 나눌 때 필요한 블루레이 개수(`k`)와 현재 블루레이에 담긴 강의 길이의 합(`sum_N`)을 초기화합니다. `k`는 최소 1개부터 시작합니다.
• `for i in range(N)`: 모든 강의를 순회하며 `mid` 크기의 블루레이에 담을 수 있는지 시뮬레이션합니다.
  • `if sum_N + arr[i] <= mid`: 현재 강의(`arr[i]`)를 현재 블루레이에 추가해도 `mid` 크기를 넘지 않으면, `sum_N`에 `arr[i]`를 더합니다.
  • `else`: 현재 강의를 추가하면 `mid` 크기를 넘는 경우입니다. 이는 새로운 블루레이가 필요하다는 의미이므로, `k`를 1 증가시키고 `sum_N`을 현재 강의 길이(`arr[i]`)로 초기화하여 새 블루레이에 첫 강의를 담습니다.
• `if k <= M`: `mid` 크기로 나눴을 때 필요한 블루레이 개수(`k`)가 `M`개 이하이면, 이 `mid`는 가능한 블루레이 크기입니다.
  • `answer = mid`: 현재 `mid`를 `answer`에 저장합니다. 이 `mid`가 현재까지 찾은 가장 작은 가능한 값일 수 있기 때문입니다.
  • `right = mid - 1`: 더 작은 블루레이 크기로도 `M`개 이하에 담을 수 있는지 확인하기 위해 탐색 범위를 왼쪽으로 줄입니다.
• `else`: `k > M`인 경우, 즉 `mid` 크기로는 `M`개 초과의 블루레이가 필요하다면, `mid`는 너무 작은 크기입니다.
  • `left = mid + 1`: 더 큰 블루레이 크기를 탐색하기 위해 탐색 범위를 오른쪽으로 줄입니다.

📌 [4] 결과 출력

print(answer)

• 이진 탐색이 종료되면 `answer`에 저장된 값이 조건을 만족하는 최소 블루레이 크기이므로, 이를 출력합니다.

---

✅ 결론 정리

• 이 코드는 **파라메트릭 서치(Parametric Search)** 기법을 활용한 이진 탐색 문제 풀이입니다. "최소/최대 값을 찾는 문제"에서 "어떤 값 X가 주어졌을 때 조건을 만족하는가?"를 판단하는 함수를 만들 수 있다면 이진 탐색을 적용할 수 있습니다.
• `left`와 `right`의 초기값 설정이 중요하며, `left`는 최소 강의 길이 중 최댓값 (가장 긴 강의), `right`는 모든 강의 길이의 총합이 됩니다.
• `while left <= right` 조건과 `answer` 변수를 통해 조건을 만족하는 최솟값을 정확히 찾아 저장합니다.
• 각 `mid` 값에 대해 강의를 블루레이에 분할하는 시뮬레이션 과정이 핵심 로직이며, 이 과정에서 `sum_N`과 `k`를 적절히 관리하여 필요한 블루레이 개수를 계산합니다.