[BOJ - 이분탐색] 14627번 : 파닭파닭 ( python )

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

14627번: 파닭파닭

백준 14627번 : 파닭파닭 (실버3)

 

문제

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

입력

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

 

---

 

1. 사고하기

• 목표 : 파닭에 파를 똑같이 넣어야 하는데, 파는 최대한 많이 넣고 파의 길이는 똑같이 들어간다.
• 남은 파는 라면에 넣는다. 라면에 넣을 파를 구하시오.
• 유형 : [이분탐색] : 파의 길이가 큰 수이기 떄문에 이분탐색으로 잘라서 최대한 큰 파의 길이를 구해야한다. 
• start = 1또는 0 (0일 경우엔 조건이 추가된다.)
• end =파의 최대 길이
• 다른 이분탐색과 같이 ( start+end ) // 2 를 mid값으로 설정하고 이 값을 파를 자르는 기준으로 사용한다. 
• 각 파의 길이를 mid값으로 나눠주면 치킨에 넣을수 있는 파의 개수값이다.  (cnt)
• cnt가 같거나 크면 충분히 파가 있는 경우이기 때문에 파의 길이를 더 늘려도 된다는 뜻이고, 이는 start 를 mid+1 해준다음, max 길이를 저장해주어야 한다. 
• cnt가 작으면 파의 개수가 부족한 상황,  파의 길이를 줄여야 한다는 뜻이고 end 값을 mid -1로 설정해 줄여준다.
• 우리의 목표는 치킨에 넣고 남은 파를 라면에 넣을때 라면에 들어가는 파의 양이기 떄문에
• 이분탐색을 마친후 resChick는 치킨에 들어간 각 파의 길이이므로 치킨의 개수(c) * resChick 는 치킨에 들어간 파의 길이이다
• 전체 sum(L) 에서 (c*resChick)을 빼주면 라면에 들어가는 파의 양이 된다.   

 

 

2. 이 문제를 공유한 이유 : start 조건을 생각하는게 어려웠다.

- start == 0으로 설정했을 때 mid == 0일 때 1로 설정해주어야 했다.   

 start = 0, end= 1인 경우에 mid값이 0이 되어서 코드 자체가 작동할 수 없다 >> mid를 1로 바꿔주면 된다.

- start == 1로 설정했을 땐 mid 조건 재설정이 필요 없었다.

>> 왠만해서 이분탐색은 1로 시작하는게 좋은것 같다는 의견! (0으로 시작하면 예외가 생기는 느낌이다... ㅠ)

 

 

 

정답 코드

1. start = 0 로 했을 때

import sys
input = sys.stdin.readline

s, c = map(int,input().split())
L = [int(input()) for _ in range(s)]

start = 0
end = 1000000000

resChick = 0

while(start<=end):
    mid = (start+end) // 2
    if mid == 0:
        mid = 1
        
    cnt = sum(pa//mid for pa in L)
    if cnt >= c: #cnt 가 같다 == mid 저장,
        # cnt의 개수가 크다는 것은 mid를 더크게 해도 된다는 것. 
        resChick = max(resChick,mid)
        start = mid+1
    else:
        end = mid -1
 
 # 전체 파의 합  - (파닭의 개수 * 치킨에 들어가는 파)      
res = sum(L) - (c * resChick)
print(res)

 

2. start = 1 ver

import sys
input = sys.stdin.readline

s, c = map(int,input().split())
L = [int(input()) for _ in range(s)]

start = 1
end = max(L)

resChick = 0

while(start<=end):
    mid = (start+end) // 2
    
    cnt = sum(pa//mid for pa in L)
    if cnt >= c: #cnt 가 같다 == mid 저장,
        # cnt의 개수가 크다는 것은 mid를 더크게 해도 된다는 것. 
        resChick = max(resChick,mid)
        start = mid+1
    else:
        end = mid -1
 
 # 전체 파의 합  - (파닭의 개수 * 치킨에 들어가는 파)      
res = sum(L) - (c * resChick)
print(res)

 

 

 

start 를 0, end 값을 1000000000 :

start 를 1, end 값을max(L)로 

시간 차이를 보니까 역시 max(L)이 훨씬 작게 나오는것을 확인할 수 있었다.