030 기타 레슨

첫번째 코드

 

이 문제의 경우는 정렬해서 중앙값을 찾아 다시 찾는 이진 탐색은 맞으나

총 합을 기준으로 생각하는 것이다!

 

예를 들어 블루레이가 3개 필요하다 할 때,

총 합의 중앙값으로 계산한 결과 블루레이가 4개이면, 중앙값 기준 시작 점을 오른쪽으로 옮기고

충 합의 중앙값으로 계산한 결과 블루레이가 2개이면, 중앙값 기준 끝 점을 왼쪽으로 옮기는 것이다.

 

읽고나면 그렇게 계산할 수 있구나~ 라고 생각이 들지만 사실 직접 풀 때 이런 아이디어를 낼 수 있을까? 가 걱정이다...

그리고 코드를 짤때도 어려움이 있어 책을 참고했다...

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
A = list(map(int, input().split()))
start = 0
end = 0

for i in A:
    if start < i:
        start = i
    end += i
    
while start <= end:
    median = int((start + end) / 2)
    sum = 0
    count = 0
    for i in range(n):
        if sum + A[i] > median:
            count += 1
            sum = 0
        sum += A[i]
    if sum != 0:
        count += 1
    if count > m:
        start = median + 1
    else:
        end = median - 1

print(start)

 

통과!

이상하게 정렬해서 중앙값을 사용하는 것이라고 쉬울 것이라고 생각했는데, 그 전에 생각해야 하는 아이디어가 어려운 것 같다...

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Silver/2343.%E2%80%85%EA%B8%B0%ED%83%80%E2%80%85%EB%A0%88%EC%8A%A8

programmers/백준/Silver/2343. 기타 레슨 at main · ornni/programmers