[백준OJ] 11052번 카드 구매하기

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

11052번: 카드 구매하기

---

 

 

-풀이-

비용을 저장하는 배열 cost와, dp배열을 선언하여 풀이를 했다.

dp[i] = K 는 i장의 카드를 사는데 드는 최댓값 K원이라는 뜻이다.

 

i장의 카드뭉치의 비용이 c라고 하자.

i장의 카드뭉치를 들고 j장을 구매했을때, 최댓값을 구하기 위해선, 먼저 i장의 카드뭉치를 사용하지 않고 구매한 비용(dp[j]의 값) 과, i장의 카드뭉치를 사용하여 j장을 구매했을때의 비용(dp[j-i]의 값+ i장의 카드뭉치의 비용 c )의 값을 비교하여, 둘중 더 큰값을 dp[j]에 갱신시켜주면 된다.

 

이를 전체로 적용시켜 문제를 해결했다.

 

-시간복잡도-

O(N²)

 

-코드-

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

int cost[1001] = { 0 };
int n;
long long dp[1001] = { 0 };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	
	for (int i = 1; i <= n; i++) {
		cin >> cost[i];
	}

	for (int i = 1; i <=n; i++) {
		int c = cost[i];
		for (int j = i; j <= n; j ++) {
			if (dp[j] < dp[j - i] + c) {
				dp[j] = dp[j - i] + c;
			}
		}
	}
	cout << dp[n];

	return 0;
}