[알고리즘/백준] 16401번 - 과자 나눠주기

16401번 과자 나눠주기 - https://www.acmicpc.net/problem/16401

 

 

카테고리 : 이분 탐색 / 매개변수 탐색

 

접근 방법

 

이 문제는 매개 변수 탐색 문제이다.

매개 변수 탐색이란 이분탐색을 사용하여 조건을 만족하는 최댓값을 구하는 방법이다.

 

1. 막대 과자 길이를 매개 변수(이분 탐색을 진행하는 대상)으로 설정한다.

--> 최소 길이 1 / 최대 길이 max(snack) 을 start와 end로 설정

 

start, end = 1, max(snack)

 

2. mid만큼 자를 때 mid 길이로 잘릴 수 있는 개수를 세어준다.

ex) 만약 길이가 11인 막대 과자를 5로 자른다면 5 / 5 / 1 로 잘리기 때문에 개수는 2개 

 

cnt = sum([snack[i] // mid for i in range(N)])

 

3. 개수가 M(조카의 수)보다 작다면 더 많이 잘라야 하고, M보다 크거나 같다면 충분하기 때문에 값을 result에 저장

 

if cnt < M:
	end = mid - 1
else:
	result = mid
	start = mid + 1

 

---

코드

 

- 최종 코드

 

import sys

def binary_search(N, M, snack):
    start, end = 1, max(snack)
    result = 0
    while start <= end:
        mid = (start + end) // 2
        cnt = sum([snack[i] // mid for i in range(N)])
        if cnt < M:
            end = mid - 1
        else:
            result = mid
            start = mid + 1
            
    return result
        

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

 

- 시간 초과 코드 (맞았는지는 알 수 없음..)

 

import sys
import math
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

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

while True:
    num = snack.pop() / 2
    if N <= M and math.floor(num) < snack[-(N-1)]:
        snack.append(num)
        break
    snack.insert(bisect_left(snack, math.floor(num)),math.floor(num))
    snack.insert(bisect_left(snack, math.ceil(num)),math.ceil(num))
    M += 1
    if snack[-N] == 0:
        break

print(snack[-N])

 

---

 

매개 변수 탐색 관련 공부 링크 

 

이진 탐색(Binary Search)과 매개변수 탐색(Parametric Search)

 

[알고리즘&코딩테스트] 매개 변수 탐색 (Parametric Search)

 

이분 탐색(Binary Search)과 매개 변수 탐색 (Parametric Search)