[백준] 2343 기타 레슨

📌문제 링크

2343 기타 레슨

💡 문제 풀이

처음에 문제 읽고 이게 뭔소리야... 함
힌트 유심히 읽어보고 이해했다

1. 구해야 하는 것 : 강의를 다 녹화할 수 있는 블루레이의 최소 크기
   (start = 0, end = 강의 길이 총합)
2. 1번을 구하는데 필요한 기준 : 블루레이 크기에 따라 강의를 '순서대로' 녹화할 수 있는지

술술 풀었다고 생각했는데
틀렸다...

📋틀린 코드

import sys
n, m = map(int, input().split())
arr = list(map(int, sys.stdin.readline().split()))


def binary_search(start, end):
    result = 0
    while start <= end:
        mid = (start + end) // 2
        total = mid  # 블루레이 크기
        cnt = m  # 블루레이 개수

        # 강의 순서대로 녹화
        for x in arr:
            # 강의 크기만큼 차감시킴
            if total >= x:
                total -= x
            # 블루레이 용량 다 채웠을 경우
            else:
                total = mid
                cnt -= 1
                # 필요한 블루레이 개수가 m개를 넘어갈 경우
                if cnt <= 0:
                    break
                else:
                    total -= x

        # 크기가 작아 강의를 다 녹화하지 못할 경우
        if cnt <= 0:
            start = mid + 1
        else:
            result = mid
            end = mid - 1

    return result


print(binary_search(1, sum(arr)))

"백준 2343번-기타 레슨" 반례 모음
이 블로그의 도움을 받았습니다...
반례 돌려보니까 틀린거 개많았음 머쓱;

틀렸던 이유!!
for문 안에서 break를 거는 기준을 블루레이를 다 썼을 때만 했었는데, 블루레이 크기가 하나의 강의 길이보다 작을 때도 포함시켜야 했다
(다른 사람들 코드 보니까 그냥 start 값을 max(arr)로 하면 됐을 것 같다..)
그리고 start, end 조정하는 부분 조건문에도 걸리게 하기 위해서 이 조건에 걸릴 경우 cnt을 -1로 만들었다

수정한 부분 :

# 필요한 블루레이 개수가 m개를 넘어갈 경우
                if cnt <= 0 or x > mid:
                    cnt = -1
                    break
                else:
                    total -= x

📋맞은 코드

# 2343 기타 레슨
import sys
n, m = map(int, input().split())
arr = list(map(int, sys.stdin.readline().split()))


def binary_search(start, end):
    result = 0
    while start <= end:
        mid = (start + end) // 2
        total = mid  # 블루레이 크기
        cnt = m  # 블루레이 개수

        # 강의 순서대로 녹화
        for x in arr:
            # 강의 크기만큼 차감시킴
            if total >= x:
                total -= x
            # 블루레이 용량 다 채웠을 경우
            else:
                total = mid
                cnt -= 1
                # 필요한 블루레이 개수가 m개를 넘어갈 경우
                if cnt <= 0 or x > mid:
                    cnt = -1
                    break
                else:
                    total -= x

        # 크기가 작아 강의를 다 녹화하지 못할 경우
        if cnt <= 0:
            start = mid + 1
        else:
            result = mid
            end = mid - 1

    return result


print(binary_search(1, sum(arr)))