[알고리즘] 11052번 백준 알고리즘붕어빵 판매하기

#include <stdio.h>

#include <iostream>

using namespace std;

int main() {

    int n;          // 입력 최대붕어

    int fish_price[1001];   // 붕어 가격

    int dp[1001];           // 붕어 저장 dp

    scanf("%d", &n);        // 붕어 수 입력

    

    // 붕어 가격 입력

    for (int i = 1; i <= n; i++){

        scanf("%d", &fish_price[i]);

    }

    

    // dp[i] = i-j번째 최댓값 + j개 세트의 가격(하나씩모두 비교하기 위해서 2중포문)

    for (int i = 1; i <= n; i++){

        for (int j = 1; j <= i; j++){

            // 최대값일경우만 dp[i]에 저장

            if (dp[i] < dp[i-j] + fish_price[j]){

                dp[i] = dp[i-j] + fish_price[j];

            }

        }

    }

    

    // 붕어 새끼 출력

    printf("%d", dp[n]);

    return 0;

}