[BaekJoon][1535] 안녕

BAEKJOON ONLINE JUDGE

1535 안녕

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

0-1 knapsack 문제

체력이 100까지므로 100에서 깎아도 되고

0에서 인사를 할 때 체력을 쌓아서 100이전, 99로 만들때 저장되는 기쁨의 최대값을 출력

strength[1]을 사용할 때 모든 체력에 저장된 기쁨에 joy[1]을 합해가면 점차 쌓여서 체력 99에 모든 값이 저장되어 있다.

#include <stdio.h>
 
#define Max(x, y)        (((x) > (y)) ? (x) : (y))
 
int n;
int strength[20], joy[20];
int dp[100];
 
int main()
{
    int i, j;
 
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) {
        scanf("%d", &strength[i]);
    }
    for (i = 0; i < n; i++) {
        scanf("%d", &joy[i]);
    }
 
    for (i = 0; i < n; i++) {
        for (j = 99; j >= strength[i]; j--) {
            dp[j] = Max(dp[j], dp[j - strength[i]] + joy[i]);
        }
    }
 
    printf("%d\n", dp[99]);
 
    return 0;
}