11052

11052번 : 카드 구매하기

🎈 문제 이해

먼저, arr[]배열에 각 카드팩 금액을 저장하고, p[]배열에는 해당 인덱스에 해당하는 카드 수를 뽑을때 최대 금액을 저장한다.
인덱스 0은 0으로 초기화 해주고, 순서대로 숫자들을 조합하며 max함수를 사용하여 비교해 최댓값을 p에 저장해 준다. 여기서 만약 3을 조합할때, 1 + 1 + 1, 1 + 2 , 3 이런식으로 조합되는 수는 3이하의 수이므로, 이것을 for문에 적용하여 구현해준다.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int N;
	cin >> N;

	int arr[10000];
	int p[1000];
	p[0] = 0;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= i; j++) {
			p[i] = max(p[i], p[i - j] + arr[j]);
		}
	}
	cout << p[N];
}