백준 16194 카드구매하기 2 - 쉬운 dp문제 c++

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

16194번: 카드 구매하기 2

우선 입력으로 받은 카드의 가격들을 arr에다가 담는다. 이것들이 기저 조건들이 된다. 

그 다음엔 2개가 들어있는 카드팩부터, n개 들어있는 카드팩을 사는게 이득인지, n-k개 카드팩 + k개 카드팩 을 사는게 이득인지를 k = 1부터 n-1까지 돌려보면 쉽게 구할 수 있다.

최대 카드팩 장수가 1000이고, O(n^2)로 코드가 돌아가기 때문에 충분히 시간내에 풀 수 있다.

#include <iostream>
using namespace std;
int n;
int arr[1001];
 
int solution(int num){
    for(int i=2; i<=num;i++){
        for(int j=1; j<i;j++){
            arr[i] = min(arr[i],arr[i-j]+arr[j]);
        }
    }
    return arr[num];
}
 
 
 
int main(void){
    cin>>n;
    for(int i=1; i<=n;i++)
        cin>>arr[i];
    cout<<solution(n);
}