[파이썬/python] 백준 14627- 파닭파닭

 

문제

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

---

문제 설명

1. 길이가 일정하지 않은 파가 S개 존재한다.
2. 파닭을 만드는데 들어가는 파의 양은 일정하다.
3. 최대한 많은 양의 파를 넣어야 한다.
4. 모든 파닭을 만들고 남은 파를 구한다.

---

풀이

파의 길이 L은 $(1 ≤ L ≤ 10^9)$이다. 따라서 완전 탐색으로 전체를 탐색하기에는 시간이 부족하다. 따라서 이분 탐색을 통해 하나당 넣을 수 있는 최대 파의 길이를 탐색했다.

 

1. start, end의 값을 초기화한다.
2. 각각의 파를 mid값으로 나눈다. -> mid 길이의 파로 현재 가지고 있는 파로 몇개의 파닭을 만들 수 있는지 구한다.
3. mid의 길이로 주문받은 파닭을 충분히 만들 수 있으면 start = mid, 그럴 수 없다면 end = mid로 변경한다.
4. 이분탐색이 끝나면 start가 최댓값이므로, 전체 파의 양 - (start * 주문받은 파닭의 수) = 남은 파의 양

---

코드

import sys
input = sys.stdin.readline

S,C = map(int,input().split())
onions = []
for i in range(S):
    onions.append(int(input()))
s = 0
e = max(onions)+1

while s+1 < e:
    mid = (s + e) // 2
    cnt = 0
    for onion in onions:
        cnt+= (onion // mid)
    if cnt >= C:
        s = mid
    else:
        e = mid

res = sum(onions)-C*s
print(res)

---

시간복잡도

• 이분탐색의 시간복잡도 = $O(\log_2n)$
• 파의 개수만큼 반복 = $O(10^6)$
• 총 시간복잡도는 약 $O(10^6*\log_2n)$
• 파의 길이가 $10^9$일 때 최악이므로 $10^9$ = $2^{30}$
• 약 $O(10^6 * log_22^{30})$ = $O(3* 10^7)$의 시간이 걸린다.