백준 11052 카드 구매하기

백준 11052 카드 구매하기

www.acmicpc.net/problem/11052

11052번: 카드 구매하기

카드 구매하기 문제의 경우 1장을 골랐을 때 최고의 가격, 2장을 골랐을 때의 최고의 가격 등을 구해주어서 문제를 해결할 수 있다. 

 

아래의 예를 보자 

 

10은 첫번째 카드, 9는 두번째 카드 ,,,, 쭉 진행한다. 

 

1번째 카드의 경우 경우의 수가 1장 뿐이다. 

 

2번째 카드 1 1, 2 자기 자체를 가지는 값

 

3번째 카드 1 2, 3 1번째 카드와 2번째 카드를 가졌을 때, 3번째 자기 자신을 가졌을 때.....

 

이렇게 각 경우의 수들 중에 가장 큰 값을 dp에 저장하면서 재활용하는 방식으로 문제를 해결하면 된다. 

#include <cstdio>
#include <algorithm>

using namespace std;

int value[1002], dp[1002];

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

	for(int i = 1; i <= N; i++)
		scanf("%d", &value[i]);

	for(int i = 1; i <= N; i++){
		for(int baseNum = 1; baseNum <= i/2; baseNum++){
			dp[i] = max(dp[baseNum] + dp[i - baseNum], dp[i]);
		}
		dp[i] = max(dp[i], value[i]);
	}

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

 

두번째 반복문이 i/2인 이유는 인덱스가 4라면 1, 3  2, 2만 가지고 있으면 되기 때문이다.