[BOJ 14627 🥈2] 파닭파닭 (Python)

https://www.acmicpc.net/problem/14627

14627번: 파닭파닭

문제

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

 

입력

첫째 줄에 승균이가 시장에서 사 온 파의 개수 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의 파가 남는다.

 

⭕ CODE

import sys

input = sys.stdin.readline

s,c = map(int,input().split())

arr = []

for _ in range(s):
    l = int(input())
    arr.append(l)

arr.sort()

# 시작지점 1
# 끝지점은 가장 큰 파의 길이
# 3 5
# 600
# 400
# 199
# 이러한 경우
# 200으로 5개를 만들어 199가 남는다
s = 1
e = arr[-1]

while s <= e:

    # 파의 길이 mid
    mid = (s + e) // 2

    # 파닭의 수와 비교하기 위한 count
    count = 0

    # 파의 길이로 나누어서 개수를 구하는 과정
    for i in arr:
        count += i // mid

    # 만약 개수가 목표 c 이상이면
    # 파의 양을 최대한 많이 넣으려 하기에
    # mid는 더 커져도 된다.
    if count >= c:
        s = mid + 1

    # 개수가 c 이하라면
    # 각각의 파닭에 못들어가므로
    # mid의 길이를 줄인다
    else:
        e = mid - 1

# 라면에 넣을 파의 양은
# 전체의 파의 양에서 (최대 파의 길이 * 파닭의 수) 를 빼줘야한다.
print(sum(arr) - c*e)

✏️ Comment

이분 탐색을 사용하여 문제 해결

처음에는 모든 파를 다 사용해야하는 줄 알고 e의 조건을 파의 길이 중 가장 짧은 것으로 지정해주었다. 그러나 반례를 생각하다 보니

3 5
600
400
199​

 

라는 반례를 생각하게 되었고 사용할 파의 길이를 200으로 하면 600cm 파에서 3개 400 cm 파에서 2개가 되므로 5개를 만족하고 남은 파의 길이는 199이다.