[백준] 2343번 파이썬 - 이분 탐색 (상세 설명)

문제요약 (2343번. 기타 레슨)

 

 

2343번: 기타 레슨

 

 

풀이를 위한 부연 설명

• 블루레이 크기가 모두 같고, 녹화 순서가 바뀌지 않아야한다를 통해 이진 탐색임을 알아야함
  • 강의 순서대로 차례로 저장하면서 해당하는 크기의 블루레이로 모든 강의가 저장되는지 확인하는 방식
  • 가능하다면 블루레이의 크기를 줄이고, 불가능하다면 블루레이의  크기를 늘임.
• 이진 탐색의 시작은 레슨의 가장 큰 강의 길이로 하여 각각 담는 경우와
• 끝은 모든 강의의 합으로 하여 모든 강의를 한 번에 담는 경우를 고려
• 해당하는 크기로 모든 강의를 담을 수 있는지 확인하는 것이 포인트!

 

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
times = list(map(int, input().split()))

start = max(times)
end = sum(times)

while start <= end:
    mid = (start + end) // 2

    tmp = 0
    cnt = 0
    for t in times:
        if tmp + t > mid:
            cnt += 1
            tmp = 0
        tmp += t

    if tmp != 0:
        cnt += 1

    if cnt > m:
        start = mid + 1
    else:
        end = mid - 1

print(start)

 

주석 상세 설명 ver.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
times = list(map(int, input().split()))

# start = 리스트 중 최댓값, end = 리스트의 총합
start = max(times)
end = sum(times)

while start <= end:
    mid = (start + end) // 2

    tmp = 0
    cnt = 0
    # 각 강의가 새 블루레이에 담아야하는지,
    # 기존 블루레이에 이어서 저장하는지 확인
    for t in times:
        # 만약 새 블루레이 써야하는 경우
        # (= 해당 하는 강의를 넣으면 블루레이 용량보다 커지는 경우) 
        if tmp + t > mid:
            cnt += 1
            tmp = 0
        # 현재 블루레이에 강의 넣기
        tmp += t

    # 만약 넣어야하는 강의가 남은 경우, 새 블루레이에 나머지 담기
    if tmp != 0:
        cnt += 1

    # 이진탐색 수행
    if cnt > m:
        start = mid + 1
    else:
        end = mid - 1

print(start)

 

기억할 점

• 이진 탐색 문제라는 것을 알아봐야하는 문제
• 블루레이에 강의를 넣을 수 있는지 판단하는 것이 중요한 아이디어

    for t in times:
        # 만약 새 블루레이 써야하는 경우
        # (= 해당 하는 강의를 넣으면 블루레이 용량보다 커지는 경우)
        if tmp + t > mid:
            cnt += 1
            tmp = 0
        # 현재 블루레이에 강의 넣기
        tmp += t

 

• 이분 탐색 후 답이 무엇인지 알아야함