[백준][11052번][DP] 붕어빵

붕어빵

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

<코드>

#include <stdio.h>
 
int boong[1001];
int boo[1001];
int main(void){
 
    int N;
    
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        scanf("%d", &boo[i]);
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++){
            if (i <= j)
                boong[j]= boong[j] > boong[j-i] + boo[i] ? boong[j] : boong[j - i] + boo[i];
        }
    }
 
    printf("%d\n", boong[N]);
 
    return 0;
}

<문제 푼 요령>

1. 붕어빵을 끊임없이 갱신하면 최대값을 저장한다.

2. 즉 boong[j] = boong[[j-i] + boo[i] 란 현재 i 값어치의 붕어빵을 넣었다고 가정했을때 이전의 값어치의 최대값에서 더하는 값이다.  즉 이전의 저장된 값이랑 이 값을 비교해서 최대값을 저장하다보면 마지막에 최대값만 남게 될 것이다.