문제 출처

1. 문제설명

• 구매하려는 카드의 개수와 금액이 주어진다.
• 카드의 개수를 맞춰서 살 때 최대 금액을 구하라
• 예제 1

  • Input

    4
    1 5 6 7
    

  • 4개의 카드팩은 각각 순서대로 1, 5, 6, 7원을 지불해야 한다.
    • 1에 해당하는 첫 번째 카드팩은 카드가 한 개
    • 5에 해당하는 두 번재 카드팩은 카드가 두 개
  • 따라서 5*2 = 10이 최대 값이 된다.

2. 알고리즘 설계

• DP 문제
• 세 개의 카드를 사야한다고 가정해보자.
  • 3번 카드를 하나 사는 경우
  • 1번, 2번 카드를 하나씩 사는 경우
  • 1번을 세번 사는 경우

3. 로직

• 점화식
  • DP[i] = max(DP[i], DP[i - j] + arr[j])
• 2. 알고리즘 설계 부분에서 언급한 걸 계산할 수 있다.

4. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int n, DP[1001], arr[1001];

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			DP[i] = max(DP[i], DP[i - j] + arr[j]);

	cout << DP[n];

	return 0;
}

5. 소감

• 이 문제또한, 금액이 매우 컸다면 자료형을 신경써야 한다.
• 최대 금액이 만원이고, N이 1000이므로, int형을 사용하였다.