[백준] 16401 과자 나눠주기

문제 설명

문제 링크

이진 탐색 문제이다. 어제 이진 탐색 문제를 시도했을 때, 이진 탐색을 사용해야 하는 것조차 생각 못해내서 관련 문제들을 여러 개 풀어 익숙해지려고 한다.

조카들이 나를 귀찮게 하는 것을 방지하기 위해 막대 과자를 주어야 하며, 최대한 오래 편하게 있고 싶기 때문에 과자의 길이 또한 최대한으로 늘려야 한다. 이 때 공평하게 나눠주어야 난리치지 않을 것이며, 이를 위해 긴 과자는 쪼갤 수 있다.

문제 풀이

우선, 저번 이분 탐색때 했던 left 와 right 설정을 최우선으로 생각했다. left값은 최소한으로 나누어줄 수 있는 길이인 1, 최대 길이는 최대한으로 줄 수 있는 과자 길이인 max(snack)으로 설정했다. 처음에는 sort()를 써서 조카의 수 만큼 인덱스를 옮겨 탐색 범위를 좁힐까도 생각했지만, 예제에서 보니 과자의 개수보다 조카의 수가 더 많을 수 있었기 떄문에 이런 방식으로 하면 인덱스 오류가 뜰테니 그냥 max값으로 설정했다.

최소와 최대 범위를 설정한 후에는 다른 이분 탐색과 같이 mid를 찾고 이를 상황에 맞게 조정하며 나누어 줄 수 있는 길이를 찾는다. mid 길이로 나누었을 떄 과자의 개수가 조카의 수보다 적어지면 나눠주지 못하기 때문에 과자를 더 짧게 해야 한다는 뜻임으로 right 범위를 내렸으며, 과자의 개수가 조카의 수보다 많으면 일단 나눠줄 수 있다는 말이니 이를 저장하고, 더 길게 만들 수 있는 경우를 고려하여 pieces >= M에는 left 끝을 올렸다.

처음에는 두 번째 예제에 답이 계속 6으로 나와 무엇이 문제였나 봤는데, 첫 코드 시도는 pieces >= M이 아닌, if, elif, else로 세 경우의 수로 분기하여 if pieces == M 에 ans를 설정하여 break하도록 되어있었기 떄문에 과자 개수가 딱 맞는 경우에 그냥 무조건 반복문을 탈출하도록 되어있었다. 당연히 길이 6으로 나누어도 모든 조카의 수만큼 공평하게 나눠줄 수 있기 때문에 이런 문제가 발생하였고, 이에 맞게 수정해주었다.

코드

import sys

input = sys.stdin.readline

M, N = map(int, input().split())
snack = list(map(int, input().split()))

#물리적으로 나눠줄 수 있는 최소와 최대 길이는?
lt = 1
rt = max(snack)
ans = 0
while lt <= rt:
    mid = (lt + rt)//2

    pieces = 0
    for i in range(len(snack)):
        pieces += snack[i]//mid
    
    if pieces >= M:
        ans = mid
        lt = mid + 1
    else:
        rt = mid - 1

print(ans)