[Silver II] 파닭파닭 - 14627

문제 링크

성능 요약

메모리: 210016 KB, 시간: 860 ms

분류

이분 탐색, 매개 변수 탐색

제출 일자

2026년 04월 25일 22:04:59

문제 설명

평소 요리에 관심이 많은 승균이는 치킨집을 개업하였다. 승균이네 치킨집은 파닭이 주메뉴다. 승균이는 가게를 오픈하기 전에 남부시장에 들러서 길이가 일정하지 않은 파를 여러 개 구매하였다. 승균이는 파닭의 일정한 맛을 유지하기 위해 각각의 파닭에 같은 양의 파를 넣는다. 또 파닭 맛은 파의 양에 따라 좌우된다고 생각하기 때문에 될 수 있는 한 파의 양을 최대한 많이 넣으려고 한다. (하지만 하나의 파닭에는 하나 이상의 파가 들어가면 안 된다.) 힘든 하루를 마치고 승균이는 파닭을 만들고 남은 파를 라면에 넣어 먹으려고 한다. 이때 라면에 넣을 파의 양을 구하는 프로그램을 작성하시오. 승균이네 치킨집 자는 정수만 표현되기 때문에 정수의 크기로만 자를 수 있다.

입력

첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1 ≤ S ≤ 1,000,000), 그리고 주문받은 파닭의 수 C(1 ≤ C ≤ 1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S ≤ C) 그 후, S 줄에 걸쳐 파의 길이 L(1 ≤ L ≤ 1,000,000,000)이 정수로 입력된다.

출력

승균이가 라면에 넣을 파의 양을 출력한다.

---

💡 해결 방법

💻 코드

 
 
 
# 평소 요리에 관심이 많은 승균이는 치킨집을 개업하였다. 승균이네 치킨집은 파닭이 주메뉴다. 승균이는 가게를 오픈하기 전에 남부시장에 들러서 길이가 일정하지 않은 파를 여러 개 구매하였다. 승균이는 파닭의 일정한 맛을 유지하기 위해 각각의 파닭에 같은 양의 파를 넣는다. 또 파닭 맛은 파의 양에 따라 좌우된다고 생각하기 때문에 될 수 있는 한 파의 양을 최대한 많이 넣으려고 한다. (하지만 하나의 파닭에는 하나 이상의 파가 들어가면 안 된다.) 힘든 하루를 마치고 승균이는 파닭을 만들고 남은 파를 라면에 넣어 먹으려고 한다. 이때 라면에 넣을 파의 양을 구하는 프로그램을 작성하시오. 승균이네 치킨집 자는 정수만 표현되기 때문에 정수의 크기로만 자를 수 있다.
 
# 입력
# 첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1 ≤ S ≤ 1,000,000), 그리고 주문받은 파닭의 수 C(1 ≤ C ≤ 1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S ≤ C) 그 후, S 줄에 걸쳐 파의 길이 L(1 ≤ L ≤ 1,000,000,000)이 정수로 입력된다.
 
# 출력
# 승균이가 라면에 넣을 파의 양을 출력한다.
 
# 예제 입력 1 
# 3 5
# 440
# 350
# 230
# 예제 출력 1 
# 145
# 힌트
# 파닭 하나당 넣을 수 있는 최대 파의 길이는 175cm으로, 440cm 파에서 2개, 350cm 파에서 2개, 230cm 파에서 1개, 총 5개의 파닭을 만들 수 있고, 각각의 파에서 90cm + 0cm + 55cm = 145cm의 파가 남는다.
 
 
import math
import sys
input = sys.stdin.readline
 
 
s, c = map(int, (input().split()))
 
list1 = []
for _ in range(s):
    list1.append(int(input()))
 
 
#print(list1)
 
ans = 0
 
l = 0
r = max(list1)
m = (l + r)//2
 
 
 
while l <= r:
    m = ((l + r) // 2)
    m = m + 1 if m == 0 else m
 
 
    tempans = sum([i // m for i in list1])
    if tempans >= c:#파개수가 더 많거나 딱 맞으면 파의 크기를 늘려!
        ans = m
        l = m + 1
        
    elif tempans < c:#파개수가 적으면 파의 크기를 줄여!
        r = m -1
        
        
 
 
# print(ans)
 
 
ans2 = 0
 
 
 
 
for i in range(0, len(list1)):
    while c > 0 and list1[i] >= ans:
        list1[i] -= ans
        c -= 1
 
ans2 = sum(list1)
 
 
print(ans2)