[백준] 28357번: 사탕 나눠주기

🔈 문제

소수전공 수업을 마무리한 찬우는 축하의 의미로 학생들에게 사탕을 나누어 주려 한다. 구체적으로, 기준이 되는 음이 아닌 정수 $X$를 정한 뒤 최종 점수가 $X$점을 넘는 학생들에게 점수가 높은 만큼 많은 사탕을 줄 것이다. 즉, $X+1$점을 받은 학생은 $1$개, $X+2$점을 받은 학생은 $2$개, $T$($T > X$)점을 받은 학생은 $T - X$개의 사탕을 받게 된다.
찬우는 학생들에게 최대한 많은 사탕을 나누어주고 싶기 때문에 기준 점수 $X$를 가능한 한 낮게 정하려 한다. 하지만, 지금 가지고 있는 돈으로는 사탕을 $K$개까지만 살 수 있기 때문에 사탕의 총 개수가 $K$개를 넘으면 안 된다.
찬우의 수업은 총 $N$명이 수강했고, $i$번째 학생은 $A_i$점을 받았다. 수강생의 수와 각 학생의 점수, 사탕의 최대 개수 $K$가 주어질 때 찬우를 위해 가능한 $X$의 최솟값을 구하는 프로그램을 작성해 주자.

 

📝입력

첫째 줄에 정수 $N$, $K$가 공백으로 구분되어 주어진다. ($1 \leq N \leq 5\times 10^5$; $0 \leq K \leq 10^{12})$ 
둘째 줄에 $N$개의 정수 $A_1, A_2, \dotsm, A_N$이 공백으로 구분되어 주어진다. $(0 \leq A_i \leq 10^{12})$ 

 

📑출력

첫째 줄에 가능한 기준 $X$의 최솟값을 출력한다.

 

📚 문제 풀이

 

X 점 보다 낮은 점수를 받은 학생들은 모두 0개의 사탕을 받게 된다. 때문에 점수를 내림차순으로 정렬하고 각 점수마다 T-X를 계산하다가 T 가 X보다 작은 경우 멈춤으로써 불필요한 연산과 시간을 줄일 수 있다. 이때 X는 이분탐색을 사용하여 찾을 수 있다. 

 

💻 코드

import sys
input = sys.stdin.readline
 
def canbe(x):
    res = 0
    for num in nums:
        if num > x:
            res += num-x
        else:
            break
 
    return res <= k
 
n,k = map(int,input().split())
nums = list(map(int,input().split()))
nums.sort(reverse=True)
 
st,ed = 0, nums[0]
res = 0
 
while st <= ed:
    mid = (st+ed)//2
    if canbe(mid):
        res = mid
        ed = mid - 1
    else:
        st = mid + 1
 
print(res)

 

🍭 시행착오

 

원트에 성공하였다

 

🔗 문제링크

28357번: 사탕 나눠주기