Baekjoon 12865 (평범한 배낭)

Baekjoon 12865, 백준 12865 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제 보기

#include <stdio.h>
#define MAX(x,y) ( (x)>(y) ? (x) : (y) )

//Knapsack Algorithm (배낭싸기 알고리즘)

// W[i]: i번 보석의 무게
// V[i]: i번 보석의 가치
// D[i][j]: i번째 보석까지 탐색, 무게 j만큼 사용했을 때 가치 최댓값

int N, K;
int W[101], V[101], D[101][100000]={0,};

int main(){
    scanf("%d %d",&N, &K);
    for(int i=1; i<=N; i++){
        scanf("%d %d", &W[i], &V[i]);
    }

    // i번째 보석을 가져간 경우:
    // D[i][j] = D[i-1][j-W[i]] + V[i]
    // i번째 보석을 가져가지 않은 경우:
    // D[i][j] = D[i-1][j]

    for(int i=1; i<=N; i++){
        for(int j=0; j<=K; j++){
            D[i][j] = D[i-1][j];
            if(j-W[i]>=0){
                D[i][j] = MAX(D[i][j], D[i-1][j-W[i]]+V[i]);
            }
        }
    }

    printf("%d",D[N][K]);
}

아주 유명한 Knapsack problem의 기본 형태 문제이다.
2차원 배열을 설정하여 동적계획법(Dynamic Programming)을 사용하는 것이 흥미로웠다.