BOJ 11052번 :: 카드 구매하기

#문제

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

11052번: 카드 구매하기

 

#작성 코드

TOP-DOWN

#include <iostream>
using namespace std;
 
int n;
int cards[1001];
int dp[1001];
 
int buy(int n){
    if( n==0 ){
        return 0;
    }
    if( dp[n]!=0 ){
        return dp[n];
    }
    
    for(int i=1; i<=n; i++){
        dp[n] = max(dp[n], buy(n-i)+cards[i]);
    }
    return dp[n];
    
}
int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>cards[i];
    }
    
    cout<<buy(n)<<'\n';
    return 0;
}

BOTTOM-UP

#include <iostream>
using namespace std;
 
int n;
int cards[1001];
int dp[1001];        // dp[i] : i개 카드 구매할 수 있는 최대 지불 금액 
 
int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>cards[i];
    }
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=i; j++){
            dp[i] = max(dp[i], dp[i-j]+cards[j]);
        }
    }
    
    cout<<dp[n]<<'\n';
    return 0;
}

##

https://ldgeao99.tistory.com/m/288 참고!!!