[백준 11052][C++] 카드 구매하기 (Silver 1)

[문제보기]

 11052. 카드 구매하기

11052번: 카드 구매하기

 

[풀이과정]

이 문제는 1장을 구매하는 경우부터 n장을 구매하는 경우까지 차례대로 올라가면서 최대값을 갱신하면서 풀어야되는

문제이다. 필자는 카드팩의 가격의 정보를 저장하는 arr[] 배열과 각 i장을 선택하는 경우에서 최대값을 저장하는 dp[]를

만들었다.

 

1장을 구매하는 경우

1장 카드팩을 사는 것이 최대값이 된다. (dp[1])

 

2장을 구매하는 경우

dp[1]에서 1장팩을 선택한 경우 vs dp[0]에서 2장팩을 선택한 경우 

둘 중의 최대값이 dp[2]가 된다. 

 

말로 풀자면 1장의 팩을 선택한 경우는 n-1장을 카드팩에서 선택을 해야한다.

2장의 팩을 선택한 경우 n-2장을 카드팩에서 선택을 해야한다.

 

따라서 점화식은 dp[n] = max(dp[n] , dp[n-i] + arr[i]) 가 된다. 

 

[소스코드]

#include <iostream>
using namespace std;

int main(){
    int dp[1001] = {0};
    int arr[1001] = {0};

    int n;
    cin >> n;

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

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

    cout << dp[n];
}

 

[해결 과정 중 실수한 부분]