백준 1535번 : 안녕 (C 언어)

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

1535번: 안녕

Code:

#include <stdio.h>
#define max(a,b) (a>b)?a:b
 
int main()
{
    int n;
    scanf("%d", &n);
    int l[21] = { 0, };
    int j[21] = { 0, };
    int h = 100;
    int dp[21][101] = { 0, };
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &l[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &j[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int k = 1; k <= h; k++)
        {
            if (k - l[i] > 0)
            {
                dp[i][k] = max(dp[i - 1][k], dp[i - 1][k - l[i]] + j[i]);
            }
            else
            {
                dp[i][k] = dp[i - 1][k];
            }
        }
    }
    printf("%d", dp[n][h]);
}

문제 설명

세준이는 성형수술을 받고 병원에 오랜 기간 입원하였습니다. 이제 세준이는 병원에 머무르는 동안 자신을 생각해주고 돌봐준 사람들에게 감사의 인사를 드릴 차례입니다.

세준이는 총 N명의 사람들에게 각각 한 번씩만 인사를 할 수 있습니다. 각 사람에게 인사를 하면 그에 따른 체력 소모(L[i])와 기쁨 획득(J[i])이 발생합니다. 세준이는 주어진 체력 내에서 최대한의 기쁨을 얻는 것이 목표입니다. 그러나 체력이 0 이하가 되면 기쁨을 느끼지 못하고 죽게 됩니다.

세준이의 초기 체력은 100이며, 초기 기쁨은 0입니다. 문제는 주어진 체력 내에서 얻을 수 있는 최대 기쁨을 계산하는 것입니다.

입력

• 첫째 줄에 사람의 수 N(≤ 20)이 주어집니다.
• 둘째 줄에는 각 사람에게 인사할 때 잃는 체력이 1번 사람부터 순서대로 주어집니다.
• 셋째 줄에는 각 사람에게 인사할 때 얻는 기쁨이 1번 사람부터 순서대로 주어집니다.

출력

• 세준이가 얻을 수 있는 최대 기쁨을 출력합니다.

코드 설명

 

1. 각 사람에게 인사할 때 잃는 체력(l)과 얻는 기쁨(j)을 배열에 저장합니다.
2. 초기 체력(h)을 100으로 설정하고, 동적 프로그래밍을 위한 2차원 배열(dp)을 초기화합니다.
3. 각 사람별로 인사할 때 체력을 고려하여 최대 기쁨을 계산합니다.
4. 마지막으로 세준이가 얻을 수 있는 최대 기쁨을 출력합니다.

knapsack problem 알고리즘을 이용.