인프런 커뮤니티 질문&답변

안녕하세요. 승환 김님!

전체적으로 잘 풀어주셨으나 몇 가지 놓치신 부분이 있습니다.

1. cur의 초기값 세팅

bluelay_length의 최대값보다 작은 값은 유효하지 않은 값을 살펴보는 것이니 cur = max(bluelay_length) - 1로 해야 합니다.

여기서 -1을 해야하는 이유는 현재 탐색하는 구조인 [False, False, False … False, True, True, … True] 구조에서 가장 오른쪽 F를 구해야 하기 때문입니다.

2. steps의 최대 범위

steps의 최대 범위를 10000으로 잡아주셨는데요.

각 강의의 길이는 최대 10,000이고, 주어지는 강의 갯수는 100,000이므로 답이 될 수 있는 블루레이 크기는 최대 10,000 x 100,000 = 10억까지 봐야합니다.

3. check 함수의 리턴

check 함수에서 count한 갯수가 문제에서 주어진 blue_nums와 같은 경우 뿐만아니라, 작은 경우도 조건을 만족하기 때문에,

check 함수가 true가 되는 조건은 count == blue_nums가 아니라, count <= blue_nums으로 수정해주셔야 합니다.

또한 만족하지 않는 경우, true가 되는 경우까지 반복하며 이분탐색을 수행하는 것이기 때문에 check가 아닌 not check 조건을 주셔야 합니다.

4. 마지막 출력값 + 1

현재 탐색하는 구조가 [False, False, False … False, True, True, … True] 입니다.

여기서 가장 왼쪽의 True를 찾는 것이기 때문에 not check()로 찾은 가장 오른쪽의 False 인덱스에서 +1을 하여 답을 출력해야 합니다.

따라서 마지막 출력값 cur에서 +1을 하여 cur+1을 출력해주시면 됩니다.

위 내용을 반영하여 수정한 코드입니다.

nums, blue_nums = map(int, input().split())
bluelay_length = list(map(int, input().split()))

def check(length):
    count = 1
    current_length = 0
    for i in bluelay_length:
        if current_length + i <= length:
            current_length += i
        else:
            current_length = i
            count += 1   
    return count <= blue_nums
 
cur = max(bluelay_length) - 1
steps = int(1e9)

while steps > 0:
    while cur + steps <= int(1e9) and not check(cur + steps):
        cur += steps
    steps //= 2

print(cur+1)

또 궁금하신 점 있으시면 언제든 질문 부탁드립니다.

감사합니다. :)

안녕하세요, 인프런 AI 인턴입니다.

제공해주신 코드를 보면, 이분 탐색을 응용하는 문제 해결 방식에 오류가 있어 보입니다. 백준 2343번 문제는 이분 탐색을 통해 최소한의 블루레이 크기를 찾는 문제입니다. 여러분이 구현하신 코드에서 check 함수는 주어진 길이로 모든 장을 녹화할 수 있는지 없는지를 판단하는 로직으로 적절합니다. 그러나 이분 탐색의 진행 과정에서 탐색 범위를 조정하는 방식에 문제가 있습니다.

오류의 핵심은 탐색 범위 설정과 탐색 조건 로직에 있습니다. cur을 시작점으로 설정하고 steps를 통해 탐색 범위를 줄여가며 최소 길이를 찾으려는 시도는 맞지만, 탐색의 시작 범위와 종료 조건 설정에 오류가 있습니다. 문제의 조건에 맞게 이분 탐색의 시작점은 블루레이의 최대 길이, 즉 bluelay_length 중 가장 큰 값으로 설정해야 하며, 종료점은 모든 길이의 합으로 설정하는 것이 일반적입니다.

또한, 이분 탐색 중 check 함수의 사용 방식에 따라, 탐색 범위를 절반씩 줄여나가며 정답을 찾아가야 합니다. 주어진 코드에서는 cur과 steps를 사용하여 탐색 범위를 변경하려고 하였으나, 이는 문제의 조건에 맞는 이분 탐색을 구현하는 올바른 방법이 아닙니다.

올바른 이분 탐색 알고리즘을 적용하여 문제를 해결하려면, 아래와 같은 접근 방식을 따라야 합니다:

1. 이분 탐색을 위한 시작점(left)을 bluelay_length의 최댓값으로, 종료점(right)을 합으로 설정합니다.
   
2. 중간점(mid)이 조건을 만족하는지 check 함수를 통해 확인합니다.
   
3. 만족한다면 더 작은 길이로도 만족하는지 확인하기 위해 종료점을 조정(right = mid - 1)하고, 만족하지 않는다면 시작점을 조정(left = mid + 1)하여 탐색 범위를 줄여 나갑니다.
   
4. 이 과정을 반복하여, 최소한의 블루레이 크기를 찾아냅니다.
   

주어진 코드를 기반으로, 이분 탐색을 적절히 적용해 다시 문제를 해결해 보시길 권장드립니다.