[백준][Python] 2343 기타 레슨

실버 1 / 이진 탐색

🎸

https://www.acmicpc.net/problem/2343

 

 

내 풀이

N, M = map(int, input().split())
guitar = list(map(int, input().split()))
s, e = max(guitar), sum(guitar)
ans = 0

while s <= e:
    total = 0 # 블루레이의 개수
    current = 0 # 현재 강의 길이의 합
    mid = (s + e) // 2

    for g in guitar:
        if current + g > mid:
            total += 1
            current = 0
        current += g

    if current > 0:
        total += 1

    if total > M: # 강의 길이를 늘려야 함
        s = mid + 1
    else:
        e = mid - 1
        ans = mid

print(ans)

 

 

코드 설명

s, e = max(guitar), sum(guitar)

 

 

s: 강의의 최소 길이

e: 강의의 최대 길이

 

s는 최대 강의 길이로 초기화하고, e는 강의 길이의 합으로 초기화한다.

무조건 가장 긴 강의를 담을 수 있어야 하며, 블루레이가 하나인 경우라면 모든 강의를 담을 수 있어야 하기 때문이다.

 

for g in guitar:
    if current + g > mid:
        total += 1
        current = 0
    current += g

 

current에 현재 강의 길이 g를 더하면서, 합이 mid(블루레이의 크기) 보다 커지면

total(블루레이의 개수)을 늘리고, current를 0으로 초기화한다.

 

if current > 0:
    total += 1

 

current가 0보다 크면 잔여 강의가 있다는 것이므로 total(블루레이의 개수)를 하나 늘린다.

 

if total > M: # 강의 길이를 늘려야 함
    s = mid + 1
else:
    e = mid - 1
    ans = mid

 

1. total(블루레이의 개수)가 M보다 많이 필요한 경우

total을 줄여야 하므로 강의 길이를 늘려야 한다. (s = mid + 1)

 

2. total(블루레이의 개수)가 M이하면, ans에 mid(블루레이의 크기)를 저장하고, 더 최선의 케이스(더 작은 블루레이 크기)가 있는지 확인하기 위해 강의 길이를 줄여야 한다. (e = mid - 1)

 

⚡️

 

이진 탐색 개념 자체가 어렵진 않은데 막상 문제에 적용해보려고 하면 어렵게 느껴지는 것 같다.

이진 탐색할 대상을 정하는 게 가장 중요한 것 같은데 많이 해보면서 익숙해져야 할 듯!

그리고 이진 탐색으로 해결하는 문제라는 걸 모르고 풀면 과연 풀 수 있을지도 의문 🤔