기타 레슨 ( 2343 번 )

2343번: 기타 레슨

 

---

🧠 알고리즘

• 이분 탐색 (Binary Search) + 시뮬레이션 (Simulation)

 

✔️ 동작 방식

문제 핵심 아이디어

• n개의 연속된 수열을 m개의 구간으로 나누어 각 구간 합의 최댓값을 최소로 만드는 문제.
• 이분 탐색으로 가능한 최대 구간 합을 탐색하며, 주어진 mid 값으로 구간을 나누었을 때 m개 이하로 나눌 수 있는지 시뮬레이션.

주요 로직 요약

1. 입력 처리
   n, m = map(int, sys.stdin.readline().rstrip().split())
   n_list = tuple(map(int, sys.stdin.readline().rstrip().split()))
2. 이분 탐색 초기값 설정
   • l = max(n_list) : 최소 구간 합은 배열의 최대값 이상이어야 함
   • r = sum(n_list) : 최대 구간 합은 배열 전체 합을 초과할 수 없음
3. 구간 나누기 시뮬레이션
   • 현재 mid 값을 최대 구간 합으로 설정
   • 배열을 순회하며 now_len에 누적
   • now_len > mid가 되면 새 구간 시작, blue_count += 1
   • blue_count > m이면 mid 값 너무 작음 → l = mid + 1
   • blue_count ≤ m이면 가능 → r = mid - 1, answer 갱신
4. 결과 반환
   • 최종 answer는 m개 이하 구간으로 나눌 때 가능한 최소 최대 구간 합

---

 

🧾 코드

import sys

def _main(n, m, n_list):
    l, r = max(n_list), sum(n_list)
    while l <= r:
        mid = (l + r) // 2

        blue_count, now_len = 1, 0
        for i in n_list:
            now_len += i
            if now_len > mid:
                blue_count += 1
                now_len = i

        if blue_count > m:
            l = mid + 1
        else:
            answer = mid
            r = mid - 1

    return answer
    

n, m = map(int, sys.stdin.readline().rstrip().split())
n_list = tuple(map(int, sys.stdin.readline().rstrip().split()))

print(_main(n, m, n_list))

---

 

⏱️ 시간 복잡도

while l <= r : 이진 탐색 ( 로그 시간 복잡도 )
	for i in n_list : 배열을 탐색하며 강의 녹화 ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )