'size'에 저장된 길이의 사탕[] 배열이 제공됩니다. 각 요소 candies[i]에는 유형 i의 사탕에 대한 번호가 있습니다. 목표는 금액에 관계없이 가능한 한 많은 사탕을 구입하는 것입니다. 조건은 다음과 같습니다 -
유형 i(0<=X[i] <=candies[i] )의 X[i]를 구매하는 경우 모든 j( 1<=j<=i )에 대해 다음 조건 중 적어도 하나는 참이어야 합니다.
-
X(j)
-
X(j)=0, 구매한 j 유형의 사탕 없음
예를 들어 이해합시다.
입력 - Arr[] ={ 1,3,5,2,6,7 }.
출력 − 구매할 수 있는 최대 사탕 − 16
설명 − i { 0,3,5,2,6,0 }
유형의 사탕 구매입력 - Arr[] ={ 5,7,7,3,4 }.
출력 − 구매할 수 있는 최대 사탕 − 10
설명 − i { 0,0,7,3,0 }
유형의 사탕 구매아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
정수 배열 candies[]는 i 유형의 사탕 수를 저장하는 데 사용됩니다.
-
변수 '크기'는 배열 캔디의 길이를 저장합니다.
-
maxCandies(int arr[], int n) 함수는 구매할 수 있는 총 사탕 수를 반환하는 데 사용됩니다.
-
먼저 우리가 마지막 종류의 사탕을 샀다고 가정해 봅시다. 구매함=arr[n-1]
-
두 번째 마지막 요소부터 시작하여 for(i=n-2;i>=0;i--)
-
변수 x는 구매할 수 있는 현재 유형의 사탕 양을 저장합니다. x=arr[i] 또는 buy-1 중 더 작은 것
-
x가 0이 아닌 경우 이를 합계에 추가합니다.
-
합계가 이전에 구매한 값보다 크면 구매한 값=x입니다.
-
구매한 결과를 반환합니다.
예시
#include <stdio.h>
int maxCandies(int arr[], int n){
int bought = arr[n - 1];
int total = bought;
// Starting from second last
for (int i = n - 2; i >= 0; i--) {
// Amount of candies of the current
// type that can be bought
int x = arr[i]<bought-1?arr[i]:bought-1;
if (x >= 0) {
total += x;
bought = x;
}
}
return total;
}
int main(){
int candies[] = { 1,2,4,3,7 };
int size = 5;
printf("Total Candies that can be bought: %d", maxCandies(candies, size));
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
Total Candies that can be bought: 13