본문 바로가기

코딩테스트/C++

[백준 C++] 11052번: 카드 구매하기

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

 

11052번: 카드 구매하기

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

www.acmicpc.net

 

dp 문제이다.

 

dp[i] = p[i]로 우선 채워준 다음

for (int i = 2;i <= n;i++) {
		for (int j = 1; j < i; j++) {
			dp[i] = max(dp[i - j] + p[j], dp[i]);
		}
	}

이 조건문을 통해 만약 n = 4라면 

 

i = 2 일때

dp[2] 는 dp[1] + p[1]값과 p[2]값을 비교한 뒤 더 큰 값을 넣어주었고

 

i = 3 일때

dp[3] 은 이전에 구한 dp[2]의 최대값과 p[1]을 더해준 값과 dp[1] + p[2] 값, p[3]의 값을 비교한뒤 가장 큰값을 넣어준다.

 

마찬가지로 i = 4일 때 까지 진행해준뒤 dp[4]를 출력해 주었다.

 

결과는 정답!

 

틀릴 줄알았는데 한번에 정답이 되어 기분이 좋았다.

 

전체 코드는 다음과 같다.

#include <iostream>
#include <algorithm>
using namespace std;
int p[10001];
int dp[10001] = { 0 };
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
 
	for (int i = 1;i <= n;i++) {
		cin >> p[i];
	}
 
	for (int i = 1;i <= n;i++) {
		dp[i] = p[i];
	}
 
	for (int i = 2;i <= n;i++) {
		for (int j = 1; j < i; j++) {
			dp[i] = max(dp[i - j] + p[j], dp[i]);
		}
	}
 
	cout << dp[n] << "\n";
 
	return 0;
}

 

dp문제를 어떻게 해결해야할지 감이 좀 잡히는거 같다.