길이가 size인 정수 배열 candies[]가 주어집니다. 각 원소 candies[i]는 i번째 종류의 사탕이 몇 개 있는지를 나타냅니다. 우리의 목표는 아래 조건을 만족하면서 가능한 한 많은 사탕을 구매하는 것입니다.
문제의 조건
i번째 종류의 사탕을 X[i]개(단, 0 ≤ X[i] ≤ candies[i])만큼 구매한다면, 모든 j(1 ≤ j ≤ i)에 대해 다음 조건 중 적어도 하나는 반드시 참이어야 합니다.
- X(j) < X(i) : j번째 종류의 구매량이 i번째 종류의 구매량보다 적다
- X(j) = 0 : j번째 종류의 사탕은 하나도 구매하지 않는다
예제로 이해하기
입력 − Arr[] = { 1, 3, 5, 2, 6, 7 }
출력 − 구매할 수 있는 최대 사탕 수 − 16
설명 − 종류별 구매량은 { 0, 3, 5, 2, 6, 0 } 입니다.
입력 − Arr[] = { 5, 7, 7, 3, 4 }
출력 − 구매할 수 있는 최대 사탕 수 − 10
설명 − 종류별 구매량은 { 0, 0, 7, 3, 0 } 입니다.
프로그램에 적용한 접근 방식
- 정수 배열 candies[]에는 i번째 종류의 사탕 개수가 저장됩니다.
- 변수 size는 배열 candies의 길이를 저장합니다.
- 함수 maxCandies(int arr[], int n)는 구매 가능한 총 사탕 수를 반환합니다.
- 먼저 마지막 종류의 사탕을 전부 구매한다고 가정합니다. 즉, bought = arr[n-1] 입니다.
- 뒤에서 두 번째 원소부터 시작하여 for(i = n-2; i >= 0; i--) 반복문으로 앞쪽을 순회합니다.
- 변수 x는 현재 종류에서 구매할 수 있는 사탕 수를 의미하며, arr[i]와 bought-1 중 더 작은 값으로 결정됩니다.
- x가 0 이상이면 그 값을 total에 더합니다.
- 이후 bought 값을 x로 갱신하여 다음 단계에서 구매 상한이 점점 줄어들도록 합니다.
- 모든 순회가 끝나면 total을 반환합니다.
이 방식은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 별도의 추가 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다.
예제 코드
#include <stdio.h>
int maxCandies(int arr[], int n){
int bought = arr[n - 1];
int total = bought;
// 뒤에서 두 번째 원소부터 순회
for (int i = n - 2; i >= 0; i--) {
// 현재 종류에서 구매할 수 있는 사탕의 양
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