문제 - 백준 14627 파닭파닭
https://www.acmicpc.net/problem/14627
문제 설명
평소 요리에 관심이 많은 승균이는 치킨집을 개업하였다. 승균이네 치킨집은 파닭이 주메뉴다. 승균이는 가게를 오픈하기 전에 남부시장에 들러서 길이가 일정하지 않은 파를 여러 개 구매하였다. 승균이는 파닭의 일정한 맛을 유지하기 위해 각각의 파닭에 같은 양의 파를 넣는다. 또 파닭 맛은 파의 양에 따라 좌우된다고 생각하기 때문에 될 수 있는 한 파의 양을 최대한 많이 넣으려고 한다. (하지만 하나의 파닭에는 하나 이상의 파가 들어가면 안 된다.) 힘든 하루를 마치고 승균이는 파닭을 만들고 남은 파를 라면에 넣어 먹으려고 한다. 이때 라면에 넣을 파의 양을 구하는 프로그램을 작성하시오. 승균이네 치킨집 자는 정수만 표현되기 때문에 정수의 크기로만 자를 수 있다.
입력
첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1 ≤ S ≤ 1,000,000), 그리고 주문받은 파닭의 수 C(1 ≤ C ≤ 1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S ≤ C) 그 후, S 줄에 걸쳐 파의 길이 L(1 ≤ L ≤ 1,000,000,000)이 정수로 입력된다.
출력
승균이가 라면에 넣을 파의 양을 출력한다.
🤨풀이를 어떻게 생각했는가?
1. 고민 과정
- 주어진 파의 길이 내에서 조건을 만족하는 가장 긴 파를 찾아야 하기 때문에 탐색이 필요하다.
- 하지만 범위가 작지 않으므로 일일이 하나씩 확인하는건 무리가 있다.
- 이분 탐색을 이용한다
- 일정 길이로 잘랐을 때 파의 개수가 조건을 만족해야 한다.
- 특정 길이를 구한 후, 파의 갯수가 몇 개 나오는지 확인해야 한다.
- 혹시나 개수가 맞다고 하더라도, 더 길게 자를 수 있으니 바로 종료하지 않는다.
2. 주요 포인트
- 조건을 만족하는 길이를 구한다 하더라도, 더 길게 자르면서 조건을 만족할 수 있기 때문에 가장 큰 값이 나올 때 까지 반복해야 한다.
3. 구현 과정
- 특정 길이로 잘랐을 때 조건을 만족하는지 확인하는 함수를 만들어야 한다.
def slice(length, scal):
cnt = 0
for i in scal:
cnt += i // length
return cnt- 이분 탐색을 통해 길이를 구해내는 함수를 만든다.
start = 1
end = max(SCALLION)
maxS = (end + start) // 2
while end >= start:
mid = (end + start) // 2
if slice(mid, SCALLION) >= C:
maxS = mid
start = mid + 1
else:
end = mid - 1
answer = sum(SCALLION) - maxS * C
- 문제의 테스트 케이스를 입력받고, 수행하는 전체 코드를 만들어준다.
#전체코드#
import sys
input = sys.stdin.readline
S, C = map(int, input().split())
SCALLION = [int(input()) for _ in range(S)]
def slice(length, scal): #특정 길이, 파의 길이가 담겨있는 배열
cnt = 0
for i in scal:
cnt += i // length #몫을 구해 총 몇개가 나오는지 확인
return cnt
start = 1
end = max(SCALLION)
maxS = 0
while end >= start:
mid = (end + start) // 2
#파의 갯수가 같거나 많다면, 더 길게 자를 수 있으므로 계속 반복한다.
if slice(mid, SCALLION) >= C:
maxS = mid
start = mid + 1
else:
end = mid - 1
# 최대 길이x필요한 파의 갯수를 빼준다.
answer = sum(SCALLION) - maxS * C
print(answer)
🤔생각
- 문제를 보고 난 후, 어떻게 풀지 생각하고, 코드를 작성하는 과정이 매우 부드러웠던 문제였습니다.
- 이분탐색에서 약간의 변형만 주어진 문제라 개념을 알고 있으면 쉬운 문제에 속한다고 생각합니다.
- 🍗파닭파닭🍗
하하