(11052)(DP) 백준 붕어빵 판매하기

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

풀이

---

붕어빵이 N개 있다고 가정하자. 1개 팔 때의 가격(arr[1]), 2개 팔 때의 가격(arr[2]), .... N개 팔 때의 가격(arr[n])이 있을 것이다. N개의 붕어빵을 모두 팔 때 얻을 수 있는 최대 수익을 구해야 한다.

먼저 dp[1]은 N개의 붕어빵 중에 1개를 팔때 얻을 수 있는 최대 이익을 담는다고 하자.

그러면 dp[0] = 0; ,

 dp[1] = arr[1]; 이라고 할 수 있다.

다음으로 N개 중 2개의 붕어빵을 팔때 얻을 수 있는 최대 이익은

dp[2] = dp[1] + arr[1] or dp[0] + arr[2] 이다.

3개의 붕어빵을 팔때 얻을 수 있는 최대 이익은

dp[3] = dp[2] + arr[1] or dp[0] + arr[3] or dp[1] + arr[2] 이다.

4개의 붕어빵을 팔때 얻을 수 있는 최대 이익은

dp[4] = dp[3] + arr[1] or dp[0] + arr[4] or dp[2] + arr[2] or dp[1] + arr[3] 이다. 

dp[i] = max(dp[i-j] + arr[j]); 로 나타낼 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
#define max(a,b) a>b ? a:b
 
int main() {
    int N;
    int arr[1001] = { 0 };
    int dp[1001] = { 0 };
    
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    dp[1] = arr[1];
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i] = max(dp[i - j] + arr[j], dp[i]);
        }
    }
    
    printf("%d", dp[N]);
 
    return 0;
 
}