DP 문제 맛보기 (카드 구매하기 1,2)

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

[DP 문제 풀기전]

- 작은 문제를 일단 풀어본다.

- 그 사이에 반복되는 문제가 있는지 살펴본다.

- 그 다음 문제를 풀때, 반복되는 것을 전 문제 것을 차용한다.

 

 

[ 접근법 ]

i장의 카드 값을 저장하는 배열(arr)과 i장의 최대 구입비를 저장하는 배열(dp)를 설정한다.

 

1장을 구매하는 방법은 다음과 같다.

- 1장 구입 (= 0장의 최대 구입비 (dp[0]) + 1장 구입(arr[1]))

 

2장을 구입하는 방법은 다음과 같다.

- 2장 구입 (= 0장의 최대 구입비 (dp[0]) + 2장 구입(arr[2]))

- 1장의 최대 구입비 (dp[1]) + 1장 구입(arr[1])

 

3장을 구입하는 방법은 다음과 같다.

- 3장 구입 (= 0장의 최대 구입비 (dp[0]) + 3장 구입(arr[3]))

- 1장의 최대 구입비 (dp[1]) + 2장 구입(arr[2])

- 2장의 최대 구입비 (dp[2]) + 1장 구입(arr[1])

 

이런 규칙으로 이루어진다.

 

0장 최대 구입비(dp[0])는 0원이기 때문에 dp[0] = 0 을 저장해주고, 반복문을 통해 구현한다.

 

[ 코드 ]

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <string>


using namespace std;


int n;
int arr[1001];
int dp[1001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

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

	/*
	dp[1] = dp[1] or dp[0]+arr[1]
	dp[2] = dp[2] or dp[1]+arr[2] or dp[0]+arr[2]
	...
	*/

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			dp[i] = max(dp[i], dp[i - j] + arr[j]); // 전에 저장된 것이 dp[i]에 들어가기 때문
		}
	}

	cout << dp[n];
	

	return 0;
}