[백준] 11502번 붕어빵 판매하기

문제

출처 : https://www.acmicpc.net/problem/11502

풀이과정

D[i] 를 붕어빵 i개를 팔아서 얻을 수 있는 최대 수익이라고 할 때,

가능한 경우를 생각해보면 붕어빵 1개를 P[1]에 팔 경우에 남은 붕어빵의 개수는 i-1개가 되는데

이 경우에 P[1]+D[i-1] 라는 생각을 할 수 있다. 하지만 D[i]는 얻을 수 있는 '최대' 수익이기 때문에 최대값만 저장해야한다. 그러므로 아래와 같은 식을 생각할 수 있다.

D[i] = max(D[i],D[i-j]+P[j])

이러한 식을 이용하면 쉽게 해결할 수 있다.

DP문제는 많이 풀어보면 감이 온다고 했는데 점점 감이 오는거 같아 기분좋다.

소스코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int N;
int D[1001], P[1001];
 
int main()
{
    cin.sync_with_stdio(false);
 
    cin >> N;
 
    for (int i = 1; i <= N; i++)
    {
        cin >> P[i];
    }
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            D[i] = max(D[i], D[i - j] + P[j]);
        }
    }
 
    cout << D[N];
 
    return 0;
}