11052 붕어빵 판매하기

#include <stdio.h>
#include <algorithm>
using namespace std;
 
#define NM 1000
 
int dp[NM+1], n, price[10001];
 
int max(int a, int b) {
    if (a < b) {
        return b;
    }
    else return a;
}
 
int main() {
    //dp[i] = 0, 0, 0, ... 으로 초기화 되어있음
    //n = 4, price[i] = 1, 5, 6, 7
 
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &price[i]);
    }
    
 
    for (int i = 1; i <= n; i++) { //i번째 사람에게
        for (int j = 1; j <= i; j++) { //1개부터 i개만큼 팔아서 가장 높은 값을 찾아 저장함
            dp[i] = max(dp[i], dp[i-j] + price[j]); //가장 높은 값을 찾는 부분 
            //dp[i](지금 최댓값)이랑 dp[i-j](i-j번째 사람에게 판 최댓값) + price[j](몇 개 팔껀지 가격)을 비교해서 지금 최댓값에 넣는다
        }
    }
    printf("%d", dp[n]);
}

i번째 사람에게 1~i개만큼 팔아서 최댓값을 구하는 DP문제다.

점화식은 dp[i] = max(dp[i], dp[i-j] + price[j]) 이렇게 나오고

dp[i] (지금 최댓값)과 dp[i-j] (i-j번째 사람에게 판 가격 최댓값) + price[j] (1세트, 2세트 ..같은 가격)을 비교해서 큰 값을 지금 최댓값에 넣는다.

풀어쓰면

테스트 케이스 1번에서

i = 1일때 

j = 1: dp[1] = max(0, 0 + 1) = 1 //붕어빵 하나면 1원

i=2일때

j=1:dp[2] = max(0, 1 + 1) = 2 //붕어빵이 2개면 1개+1개 는 2원

j=2:dp[2] = max(2, 0 + 5) = 5 //2개 파는건 5원

i=3일때

j=1: dp[3]=max(0, 5 + 1) = 6 //붕어빵이 3개면 2개+1개 파는 것은 6원

j=2: dp[3]=max(6, 1 + 5) = 6 //1개+2개 6원

j=3: dp[3]=max(6, 0 + 6) = 6 //3개 세트 파는 것도 6원

i=4일때

j=1: dp[4] = max(dp[4], dp[3] + price[1])

j=2: dp[4] = max(dp[4], dp[2] + price[2])

j=3: dp[4] = max(dp[4], dp[1] + price[3])

j=4: dp[4] = max(dp[4], dp[0] + price[4])

i=4일때

j=1: dp[4] = max(0, 6 + 1) =7 //붕어빵이 4개일 때 3개+1개 파는건 7원이다

j=2: dp[4] = max(7, 5 + 5) = 10 //2개 2개 파는건 10원

j=3: dp[4] = max(10, 1 + 6) = 10 //1개+3개 =똑같이 7원

j=4: dp[4] = max(10, 0 + 7) = 10 //4개 = 7원

따라서 2개 2개 파는게 가장 이득이다.

이렇게 나오는 것이다.