백준 16401 - 과자 나눠주기( Python )

https://www.acmicpc.net/problem/16401

16401번: 과자 나눠주기

 

이진탐색으로 풀이가 가능한 파라메트릭 서치형식의 문제이다.

 

이진탐색으로 풀이를 생각하는 것은 어렵지 않았던 반면

과자하나를 어떻게 여러번 잘라야하나라는 생각이 쉽게 들지 않앗다.

나누기를 이용하면 되는 간단한 수준이였음에도 불구하고 아직 풀이 방향성을 잡는데 시간이 오래 걸린다.

 

풀이는 매우 간단하다

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

result = 0

# 0부터 시작하는 경우 zero division 에러 생기는데 그거 방지해줄거 아니면 1부터 시작해도 된다.
start = 1 
#과자값보다 큰 경우는 탐색하지않음
end = max(snacks) 

# 탐색할때 start랑 end가 같은 경우에도 비교진행을 해야함
while start <= end: 
    mid = (start + end) // 2
    #조카 수만큼 과자를 나눠줘야하므로 자른 과자 수를 카운팅 할 변수
    count = 0 
    for snack in snacks:
    	# 과자가 중간값보다 큰 경우에만 과자를 자름
        if snack >= mid: 
            count += (snack // mid)
            
    if count >= m: 
        result = mid
        # 자른 과자의 수가 조카의 수보다 큰 경우 미드값을 증가시켜서 다시 탐색
        start = mid + 1
    else: 
    	# 작은 경우 미드값을 감소 시킨다.
        end = mid - 1

print(result)