문제 설명
batchSize 값과 배열 groups가 주어진다고 가정해 봅시다. 여기서 groups[i]는 groups[i]명의 손님으로 이루어진 그룹이 가게를 방문한다는 의미입니다. 어떤 도넛 가게는 지정된 batchSize만큼씩 도넛을 만들며, 한 가지 규칙이 있습니다. 바로 현재 배치의 도넛을 모두 판매하기 전에는 다음 배치의 도넛을 판매할 수 없다는 것입니다. 또한 각 손님은 정확히 도넛 하나씩을 받게 됩니다.
한 그룹이 가게에 들어오면 다음 그룹을 응대하기 전에 해당 그룹의 모든 손님에게 도넛을 제공해야 합니다. 그리고 그룹의 첫 번째 손님이 이전 그룹이 남긴 도넛을 받지 않고 모든 멤버가 갓 만든 신선한 도넛을 받았을 때, 그 그룹은 '행복한 그룹'이 됩니다.
그룹의 순서는 마음대로 재배열할 수 있으며, 우리가 구해야 하는 것은 재배열 후 행복한 그룹 수의 최댓값입니다.
예를 들어 batchSize = 4, groups = [2,1,8,4,3]이라고 하면 출력은 4가 됩니다. 그룹을 [8,4,2,3,1] 순서로 재배열하면 첫 번째, 두 번째, 세 번째, 네 번째 그룹이 모두 행복합니다. 첫 번째 그룹을 위해 도넛 두 배치를 만들고, 두 번째 그룹을 위해 한 배치를 만들며, 세 번째와 네 번째 그룹에도 각각 한 배치씩 새로 만들어 제공하면 되기 때문입니다.
해결 접근 방식
이 문제는 각 그룹의 인원을 batchSize로 나눈 나머지만이 결과에 영향을 준다는 점에 착안하여 동적 계획법(DP)으로 풀 수 있습니다. 풀이 과정은 다음과 같습니다.
- l := groups의 각 원소 g를 batchSize로 나눈 나머지(g mod batchSize)들의 리스트
- count := l의 각 원소 빈도수를 담은 맵
- g := 0부터 batchSize-1까지 각 i에 대한 count[i]의 리스트
- dp(sm, t) 함수를 정의합니다.
- t의 최댓값이 0이면(더 이상 남은 그룹이 없으면) 0을 반환합니다.
- ans := 0, arr := t로 초기화합니다.
- k를 0부터 batchSize-1까지 반복합니다.
- arr[k]가 0이면 다음 반복으로 넘어갑니다.
- arr[k]를 1 감소시킨 뒤, ans를 ans와 dp((sm + k) mod batchSize, arr) 중 더 큰 값으로 갱신합니다.
- arr[k]를 다시 1 증가시켜 원래 상태로 복구합니다.
- 마지막으로 ans에 (sm이 0이면 1, 아니면 0)을 더해 반환합니다.
- 메인에서는 dp(0, g)를 반환합니다.
여기서 sm은 현재 배치에 이미 채워진 도넛 수를 batchSize로 나눈 나머지를 의미합니다. 어떤 그룹이 서비스를 시작하는 시점에 sm이 0이라면, 그 그룹의 첫 손님이 새 배치의 첫 도넛을 받게 되므로 그룹 전체가 신선한 도넛을 받아 행복할 수 있습니다.
구현 예제
다음 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.
from collections import Counter
def solve(batchSize, groups):
l = [g % batchSize for g in groups]
count = Counter(l)
g = [count[i] for i in range(batchSize)]
def dp(sm, t):
if max(t) == 0:
return 0
ans, arr = 0, list(t)
for k in range(batchSize):
if arr[k] == 0:
continue
arr[k] -= 1
ans = max(ans, dp((sm + k) % batchSize, arr))
arr[k] += 1
return ans + (sm == 0)
return dp(0, g)
batchSize = 4
groups = [2, 1, 8, 4, 3]
print(solve(batchSize, groups))
참고로, 그룹 수가 많아질 경우 functools.lru_cache 데코레이터를 dp 함수에 적용해 메모이제이션을 활용하면 중복 계산을 줄여 실행 속도를 크게 향상시킬 수 있습니다.
입력
4, [2,1,8,4,3]
출력
4