Dynamic Programming

Dynamic Programming

1. input size에 대해
2. base step
3. optimal substructure 찾기
   1. 문제 정의
   2. 자신보다 작은 substructure에 대한 값이 memorization되어 있다.
   3. n size → base step으로 가는 structure가 존재하는가?

백준 예제

카드 구매하기

11052번: 카드 구매하기

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    int i, j, N, *P, *M, tmp;
    scanf("%d", &N);

    P = (int*)malloc(sizeof(int)*(N+1));
    for(i=1; i<=N; i++){
        scanf("%d", &P[i]);
    }

    M = (int*)malloc(sizeof(int)*(N+1));
    M[1] = P[1];

    for(i=2; i<=N; i++){
        tmp = P[i];
        for(j=1; j<=i-1; j++){
            if(M[j]+P[i-j] > tmp){
                tmp = M[j]+P[i-j];
            }
        }
        M[i] = tmp;
    }

    printf("%d\n", M[N]);

    free(P);
    free(M);

    return 0;
}

$$
M[i]=\max\begin{cases}
P[i] \
\underset{1\le k \le {i-1}}\max(M[k]+P[i-k])
\end{cases}
$$

• $i$ 개의 카드팩을 사는 데에 드는 돈을 $P[i]$ 라고 하자 $(1 \le i \le N)$
• $i$ 개의 카드를 갖기 위해 지불해야 하는 금액의 최댓값을 $M[i]$ 라고 하자
• $M[1]=P[1]$