batchSize 값이 있고 groups[i]가 매장을 방문할 그룹[i] 고객 그룹이 있음을 나타내는 배열 그룹이 있다고 가정합니다. 그래서 주어진 batchSize의 배치로 도넛을 굽는 도넛 가게가 있습니다. 그러나 한 가지 규칙이 있습니다. 다음 배치의 도넛을 제공하기 전에 배치의 모든 도넛을 제공해야 합니다. 그리고 각 고객은 정확히 하나의 도넛을 받게 됩니다. 한 그룹이 가게에 들어올 때, 그 그룹의 모든 고객들은 다음 그룹에 연설하기 전에 서비스를 받아야 합니다. 한 그룹은 모두 신선한 도넛을 먹으면 행복할 수 있습니다. (즉, 그룹의 첫 번째 고객은 마지막 그룹에서 남은 도넛을 받지 않습니다.)
그룹을 재배열할 수 있고, 마지막으로 그룹을 재배열한 후 가능한 최대 행복 그룹 수를 찾아야 합니다.
따라서 입력이 batchSize =4 groups =[2,1,8,4,3]과 같으면 출력은 [8,4,2,3,1]과 같이 재정렬할 수 있으므로 먼저 4가 됩니다. 두 번째, 세 번째, 네 번째 그룹은 행복합니다. 첫 번째 그룹에는 두 개의 도넛 배치, 두 번째 그룹에는 하나의 배치를 만들고, 한 배치를 만든 다음 세 번째 그룹에, 다른 하나는 네 번째 그룹에 제공할 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
l :=그룹의 모든 g에 대해 (g mod batchSize)가 있는 목록
-
count :=l
요소의 빈도를 포함하는 맵 -
g :=범위 0에서 batchSize까지의 모든 i에 대한 count[i] 목록
-
dp() 함수를 정의합니다. sm, t
-
t의 최대값이 0과 같으면
-
0 반환
-
-
답변 :=0
-
arr :=t
-
범위 0에서 batchSize - 1까지의 k에 대해 수행
-
arr[k]가 0과 같으면
-
다음 반복으로 이동
-
-
arr[k] :=arr[k] - 1
-
ans :=ans 및 dp((sm + k) mod batchSize, arr)
의 최대값 -
arr[k] :=arr[k] + 1
-
-
+(sm이 0과 같으면 1, 그렇지 않으면 0을 반환)
-
기본 메서드에서 dp(0, g)
를 반환합니다.
예
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
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)) 입력
4, [2,1,8,4,3]
출력
4