N개의 다른 유형의 사탕을 이용할 수 있고 N개의 다른 유형의 사탕 가격이 모두 나와 있는 사탕 가게가 있다고 가정합니다. 상점은 또한 매력적인 제안을 제공합니다. 이 제안에 따르면, 우리는 상점에서 사탕 하나를 구입하고 다른 종류의 사탕을 최대 K개까지 무료로 얻을 수 있습니다. N개의 다른 종류의 사탕을 모두 사기 위해 지출해야 하는 최소 금액을 찾아야 합니다. 또한 N개의 다른 종류의 사탕을 모두 사기 위해 지출해야 하는 최대 금액을 찾아야 합니다. 두 경우 모두 제안을 활용하고 가능한 최대 사탕을 회수해야 합니다. k개 이상의 캔디를 사용할 수 있는 경우 모든 캔디 구매에 대해 k 캔디를 선택해야 합니다. 그러나 k보다 적은 캔디가 있는 경우 캔디 구매를 위해 모든 캔디를 선택해야 합니다.
따라서 입력이 price =[4, 3, 2, 5] 및 k =2와 같으면 출력은 최소 =5 및 최대 =9가 됩니다. 이는 k가 2일 때 사탕 하나를 구입하고 우리는 무료로 최대 2개를 더 받을 수 있습니다. 첫 번째 경우에 우리는 가격이 2인 사탕을 사서 가격이 4와 5인 사탕을 무료로 받을 수 있으며, 또한 3인 경우에도 사탕을 살 수 있으므로 최소 비용 =2 + 3 =5입니다. 반면에 두 번째 경우에는 만약 우리가 5불짜리 사탕을 사서 2불과 3불짜리 사탕을 공짜로 먹거나 4불짜리 사탕을 살 수도 있습니다. 따라서 최대 비용 =4 + 5 =9.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
get_min() 함수를 정의합니다. A,k
가 소요됩니다. -
n :=A의 크기
-
목록 정렬 A
-
해상도 :=0, i:=0
-
n이 0이 아닌 동안 수행
-
해상도 :=해상도 + A[i]
-
n :=n-k
-
나는 :=나는 + 1
-
-
반환 해상도
-
함수 get_max() 를 정의합니다. A, k
가 소요됩니다. -
n :=A의 크기
-
목록 정렬 A
-
해상도 :=0, IDx :=0
-
i:=n-1
-
동안 i>=idx, 수행
-
해상도 :=해상도 + A[i]
-
idx :=idx + k
-
나는 :=나는 - 1
-
-
반환 해상도
-
주 메서드에서 이 두 함수를 호출하여 결과를 얻습니다.
-
get_min(A, k)
-
get_max(A, k)
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def get_min(A,k): n = len(A) A.sort() res = 0 i=0 while(n): res += A[i] n = n-k i += 1 return res def get_max(A, k): n = len(A) A.sort() res = 0 idx = 0 i=n-1 while(i>=idx): res += A[i] idx += k i -= 1 return res A = [4, 3, 2, 5] k = 2 print(get_min(A, k),get_max(A, k))
입력
[4, 3, 2, 5], 2
출력
5 9