숫자 리스트 piles와 값 k가 주어졌다고 가정해 봅시다. piles[i]는 i번째 돌 무더기에 놓여 있는 돌의 개수를 의미합니다. 매시간마다 우리는 임의의 무더기를 하나 골라 그곳에서 r개의 돌을 제거합니다. 만약 선택한 무더기에 남아 있는 돌이 r개보다 적더라도, 그 무더기를 비우는 데에는 여전히 1시간이 소요됩니다.
이때 우리가 구해야 하는 것은 k시간 이내에 모든 돌을 제거할 수 있는 r의 최솟값입니다.
예를 들어 입력이 piles = [3, 6, 4], k = 5라고 해 보겠습니다. 이 경우 출력은 3이 됩니다. 시간당 r = 3개씩 제거하면 두 번째 무더기(6개)를 2시간에, 세 번째 무더기(4개)를 2시간에, 첫 번째 무더기(3개)를 1시간에 치울 수 있어 총 5시간이면 충분하기 때문입니다.
접근 방법: 이진 탐색
r이 커질수록 전체 작업을 마치는 데 필요한 시간은 줄어듭니다. 즉, r과 필요 시간 사이에는 단조 감소 관계가 성립하므로, 가능한 r의 범위에서 이진 탐색(binary search)을 적용하면 효율적으로 최솟값을 찾을 수 있습니다.
탐색 범위의 하한은 1, 상한은 가장 큰 무더기의 돌 개수입니다. 상한을 최댓값으로 잡으면 어떤 무더기든 1시간 안에 비울 수 있기 때문입니다.
알고리즘 단계
- l := 1로 초기화합니다.
- h := piles의 최댓값으로 설정합니다.
- r := h로 초기화합니다.
- turns(r) 함수를 정의합니다. 각 무더기 b에 대해 ceil(b / r)의 합을 반환하며, 이는 해당 속도로 모든 무더기를 비우는 데 걸리는 총 시간입니다.
- 메인 로직에서 l < h인 동안 다음을 반복합니다.
- mid := (l + h) // 2
- turns(mid) > k이면 속도가 부족한 것이므로 l := mid + 1
- 그렇지 않으면 h := mid로 범위를 좁히고, r := min(r, mid)로 후보 값을 갱신합니다.
- 최종적으로 r을 반환합니다.
예제 코드
from math import ceil
def solve(piles, k):
l = 1
h = max(piles)
r = h
def turns(r):
return sum(ceil(b / r) for b in piles)
while l < h:
mid = (l + h) // 2
if turns(mid) > k:
l = mid + 1
else:
h = mid
r = min(r, mid)
return r
piles = [3, 6, 4]
k = 5
print(solve(piles, k))입력
[3, 6, 4], 5
출력
3
복잡도 분석
turns 함수 한 번의 호출은 모든 무더기를 순회하므로 O(n)의 시간이 걸리고(n은 무더기의 개수), 이진 탐색은 최대 O(log m)번 호출됩니다(m은 가장 큰 무더기의 돌 개수). 따라서 전체 시간 복잡도는 O(n log m)이며, 추가 공간은 상수 수준으로 O(1)입니다.