[백준] 16401번: 과자 나눠주기 (python)

16401번: 과자 나눠주기

---

문제 )

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

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

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

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을 출력한다.

 

 

 

 

 

 

풀이)

 

오랜만에 알고리즘을 풀어서인지, 머리속으로는 정리가 되는데 표현이 잘 안되었던 것 같다.

 

이 문제는 매개 변수 를 이용한 이분탐색 문제로, parametric search 문제이다.

 

일반적인 이진탐색 문제에서 약간 추가된 느낌으로 풀면 되는데

 

해당 mid값에서 값이 참이 나올 경우, 해당 mid값에 대한 check함수가 False가 나올 때까지 이진탐색을 반복해 주면 된다.

 

이 문제에서는 check함수를 통해 mid가 과자를 충분히 조카들에게 나눠줄 수 있음에도, 나눠줄 수 없는 값이 나올때까지 계속해서 

 

계산을 반복해 나눠줄 수 있는 최대 과자값을 구하도록 했다.

 

# 과자를 충분히 나눠줄 수 있는지 체크하는 함수
def check(x):
    total = 0
 
    for i in li:
        total += i // x
    # 과자의 수가 조카의 수보다 많으면 참
    return total >= n
 
n, m = map(int, input().split())
li = list(map(int, input().split()))
 
# 이진 탐색
s = 0
e = 10000000000
 
while s <= e:
    # 만약 같은 길이의 과자를 나눠줄 수 없다면,
    # s + e가 0이라는 말이므로, zerodivision error가 나오기 전에
    # 0을 출력하고 함수를 종료한다.
    if (s + e) == 0:
        print(0)
        exit()
 
    mid = (s + e) // 2
 
    if check(mid):
        ans = mid
        s = mid + 1
    else:
        e = mid - 1
 
print(ans)

 

---

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

16401번: 과자 나눠주기