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

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

11052번: 카드 구매하기

 

기본 DP 문제입니다. 

 

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

int N, P[1001], dp[1001];

void solve(){
	for(int i = 1; i <= N; ++i){
		for(int j = 1; j <= i; ++j){
			dp[i] = max(dp[i], dp[i-j] + P[j]);
		}
	}
	cout << dp[N];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	
	for(int i = 1; i <= N; ++i){
		cin >> P[i];
	}
	
	solve();
}

 

dp 문제는 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3단계로 일관성있게 풀이합니다.

 

1) table 정의

dp[i] : i개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값

 

2) 점화식 찾기

for(int i = 1; i <= N; ++i){
    for(int j = 1; j <= i; ++j){
        dp[i] = max(dp[i], dp[i-j] + P[j]);
    }
}

1-based index를 사용하면 i = 0 부분이 경계치 역할을 하여(dp[0] = 0) 비교적 간편하게 점화식을 세울 수 있습니다.

카드가 j개 들어있는 카드팩을 선택할 때 지불해야 하는 금액을 비교합니다.  카드가 j개 들어있는 카드팩의 가격(P[j]) + 카드를 i개 구매해야 하므로 (i-j)개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값(dp[i-j]) 중에서 최대가 되는 금액으로 dp[i]의 값에 저장합니다. (1 ≤ j ≤ i)

 

3) 초기값 설정

전역변수로 배열을 선언했기 때문에 0으로 값이 초기화되므로 따로 설정할 필요가 없습니다. (입력으로 주어지는 카드의 금액들은 1 이상이므로 dp값이 0으로 초기화되어 있으면 max 연산이 원하는대로 잘 수행됩니다.)
만약 테스트케이스가 여러 개 주어지는 문제일 경우 solve() 함수 최상단에 memset(P, 0, sizeof(P)); 을 통해 dp배열의 값을 0으로 초기화하면 됩니다. 리마인드할 점은 memset으로 초기화가 가능한 값은 0, -1, 0x3f, 0x7f 등으로 매우 제한적입니다.

 

시간복잡도는 O(N^2)입니다.