[항해99 TTL]백준 16401번 문제

이 문제는 이진탐색, 매개변수 탐색 알고리즘이다.

M, N = map(int, input().split())  # 입력으로 과자 개수(N)와 조카의 수(M)를 받아옵니다.
ls = list(map(int, input().split()))  # 과자를 리스트로 받아옵니다.

def binary_search(array):
    min = 1  # 이분 탐색의 최솟값
    end = max(ls)  # 이분 탐색의 최댓값

    while min <= end:  # 이분 탐색 수행
        cnt = 0  # 나눠줄 수 있는 조카의 수와 비교할 cnt
        mid = (min + end) // 2  # 현재의 중간값을 계산합니다.

        for cookie in ls:  # 리스트의 모든 과자에 대해 반복합니다.
            cnt += cookie // mid  # 조카의 수와 비교할 변수

        if cnt >= M: 
            min = mid + 1 
        else:  
            end = mid - 1 

    return end  # 이분 탐색이 끝난 후 end값을 반환합니다.

print(binary_search(ls))  # 함수에 리스트 ls를 전달하여 이분 탐색을 수행한 결과를 출력합니다.

 

문제 설명

 - 핵심 알고리즘

 이 문제에서 핵심은 1개 과자 = 1인 이 아니라, 1개 과자 = n명 분배가 가능하다. 

그러므로 과자 / 비교값(이 코드에선 min) 의 몫의 합이 n(조카수) 보다 큰 지를 봐야한다.

 

- 이진탐색 VS 매개변수 탐색?

 이 문제는 안 쓰이는 부분은 필요 없다.

그러니 매개변수 탐색으로 해서 필요없는 부분은 버려야한다.

 

회고

 1개 과자를 n명이 나눌 수 있는 부분을 어떻게 처리할지 모르겠어서 결국 다른사람의 정답을 보았다.

이진탐색(매개변수탐색) 알고리즘은 2가지가 중요한 것 같다.

• 기준값을 잘 설정하자 : 기본배열에서 탐색할 부분을 잘 설정하기 위해
• 반복문 혹은 재귀함수 부분에서 끝나는 부분 설정을 잘하자 : 자기 코드에 따라 조건이 달라질 수 있다. 이점 꼭 유의하자