11052 - 카드 구매하기

다이나믹 프로그래밍 문제입니다.

 

최댓값을 고르는 문제인데, 처음엔 가격 위주로 생각하기 보단, 그 카드의 갯 수를 어떻게 만드는지를 고민해봅시다.

 

N개의 카드 뭉치를 만들 땐, 이전 뭉치에서 한 장을 더해서 N개를 만들거나, 두 장을 더해서 N개를 만들 수 있습니다.

 

그렇게 쭉 가다보면 N 장을 더해서 N개를 만들 수 있겠죠

 

즉, card[N] = card[N - 1] + card[1] / card[N - 2] + card[2] / card[N - 3] + card[3] ... / card[N- N] + card[N] 이런 식으로 되겠죠.

 

그렇다면 최댓값은 뭘까요?

 

그 이전의 최대 비용에서 카드를 더할 수 있는 경우의 수를 더하면 됩니다. 최대 비용과 그 이전의 카드에서 지금의 카드 장 수를 맞추기 위한 가격을 더한 것들 중 최댓값이 N장을 만들기 위한 최댓값이 됩니다.

 

그렇다면 수식으로 표현해봅시다.

 

우선, 주어진 prices와 다이나믹 프로그래밍을 위한 dp 배열이 있다고 가정합시다.

 

N 장을 만들기 위한 최댓값은 dp[N] = max(dp[N - 1] + prices[1], dp[N - 2] + prices[2], dp[N - 3] + prices[3] ... + dp[N - N] + prices[N])입니다.

 

이거 이용하면 풀려요.

 

#include <stdio.h>
#include <malloc.h>

int main(void) {
	int N;
	scanf("%d", &N);

	int max;

	int* arr = (int*)malloc(sizeof(int) * (N + 1));
	
	arr[0] = 0;

	int index = 1;

	while (index != N + 1) {
		scanf("%d", &arr[index]);
		index += 1;
	}

	int* dp = (int*)malloc(sizeof(int) * (N + 1));

	dp[0] = 0;
	dp[1] = arr[1];
	

	for (int i = 2; i < N + 1; ++i) {
		max = 0;
		for (int j = 0; j <= i; ++j) {
			if (max < dp[i - j] + arr[j]) {
				max = dp[i - j] + arr[j];
			}
		}
		dp[i] = max;
	}

	printf("%d", dp[N]);
}