BAEKJOON #16401 과자 나눠주기 (binary Search) - python

nathan·2021년 10월 16일

알고리즘문제

목록 보기

76/102

과자 나눠주기

시간 제한	메모리 제한
1초	256MB

문제

명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.

조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.

그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.

M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.

단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.

입력

첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1,000,000,000) 를 만족한다.

출력

첫째 줄에 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 출력한다.

단, 모든 조카에게 같은 길이의 막대과자를 나눠줄 수 없다면, 0을 출력한다.

입출력 예시

예제 입력 1

3 10
1 2 3 4 5 6 7 8 9 10

예제 출력 1

8

예제 입력 2

4 3
10 10 15

예제 출력 2

7

풀이

생각 및 풀이 설명

이진 탐색(Binary Search)을 이용하여 해결하였다.
start를 0, end를 가장 긴 과자의 길이로 두었다.
과자들을 모두 돌면서 mid보다 크거나 같으면 total에 snack//mid 값을 더해준다. (mid로 나누어진 수를 더하기)
total이 나눠야 하는 명수보다 크거나 같다면, result를 mid로 업데이트 하고 start 를 mid + 1로 update한다.
여기서 느낀건 과자를 모두 돌 때, sort를 하면 break를 통해 for문을 탈출하니 시간 복잡도를 더 줄일 수 있다고 생각했으나, 오히려 n이 커질 수록 sort에 nlogn만큼의 시간 복잡도가 더 걸려서 for 문 탐색 횟수를 줄여도 시간이 더 걸리는 문제점을 발견했다.
이진 탐색이라고 해서 무조건 탐색하는 배열을 정렬상태로 둘 필요는 없다. 이 문제가 대표적인 문제로써, mid를 기준으로 하여 내부에서 for문을 돌아 결국 필요한 조건에 따라 배열의 원소를 탐색한다.

python code

# 백준 16401번 과자 나눠주기
from sys import stdin
import copy
import heapq
input = stdin.readline

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

start = 0
end = max(snacks)

result = 0
snacks.sort(reverse=True)       # sort를 하니까 더 오래걸렸음 ... n log n 이라서 그런듯

while (start <= end):
    total = 0
    mid = (start + end)//2
    if mid == 0:
        break
    
    for snack in snacks:        # sort 안했을 땐 k*n 만큼의 시간이 걸림 (n이 클 수록 k*n < n*logn)
        if snack >= mid:
            total += (snack//mid)
        else:
            break
        
    if total >= m:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)