백준 11052번 - 붕어빵 판매하기

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

O(N^2) 안에 문제를 해결할 수 있는 dp 문제이다.

문제에 접근하는 방법은 1개 세트일 때 값을 구한 뒤에 2개, 3개 세트 일 때 기존에 구한 가격을 비교한 뒤에 수정해주는 것이다.

예를 들어 10개가 있을 때 각각을 모두 1개의 가격으로 구했다고 생각해보자.

그다음에 2개 세트의 가격을 반영하면 
2개일 때 : 2개일 때와 1+1개 일 때를 비교해 주면 된다.
3개일 때 : 2개+1개일 때와 1+1+1개 일 때를 비교해 주면 된다.

위의 과정을 n 개일 때까지 모두 비교해 주면 문제를 해결할 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    
    int n;
    cin>>n;
    
    int arr[1001]={0};
    int dp[1001]={0};
    
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);
    
    //0+1,1+1,2+1,3+1...
    //0+2,1+2,2+2...
    //0+3,1+3,2+3...
    for(int i=1;i<=n;i++){
        for(int j=0;j+i<=n;j++){
            if(dp[j]+arr[i]>dp[j+i])
                dp[j+i]=dp[j]+arr[i];
        }
    }
    
    cout<<dp[n]<<endl;
    
    return 0;
}