[백준] 1535 - 안녕

1. 문제

1535번: 안녕

2. 개요

N명의 사람에게 인사를 하려고 한다.

한 사람당 한 번씩만 인사할 수 있으며 각각 인사를 하면 체력을 소모하여 기쁨을 얻는다.

현재 체력은 100으로 체력이 100이하가 되면 얻은 기쁨이 0가 된다.

각각의 사람에게 인사 할 때 소모되는 체력과 얻는 기쁨이 주어졌을 때, 얻을 수 있는 최대 기쁨을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

배낭문제.

버틸 수 있는 체력의 한도는 99까지이다. 따라서 각 사람에 대해 99까지인 2차원 배열을 dp테이블로 만들어둔다.

각 사람마다 0부터 99까지 탐색한다.

dp테이블의 값을 최대 기쁨으로 갱신해나간다.

모든 탐색이 끝났다면 dp테이블 마지막 인덱스의 값을 출력한다.

3-2. Python

import sys

N = int(sys.stdin.readline())

dmgs = list(map(int, sys.stdin.readline().split()))
joys = list(map(int, sys.stdin.readline().split()))

dp = [[0 for i in range(100)] for i in range(N + 1)]

for i in range(1, N + 1):
    for j in range(100):
        if j >= dmgs[i-1]:
            dp[i][j] = max(dp[i-1][j], joys[i-1] + dp[i-1][j - dmgs[i-1]])

        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][-1])

3-3. C#

namespace boj_1535
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int N = int.Parse(sr.ReadLine());

            int[] dmgs = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            int[] joys = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

            int[,] dp = new int[N + 1, 100];

            for (int i = 1; i < N + 1; i++)
            {
                for (int j = 0; j < 100; j++)
                {
                    if (j >= dmgs[i - 1])
                        dp[i, j] = (int)MathF.Max(dp[i - 1, j], joys[i - 1] + dp[i - 1, j - dmgs[i - 1]]);

                    else
                        dp[i, j] = dp[i - 1, j];
                }
            }

            sw.WriteLine(dp[N, 99]);
            sw.Close();
        }
    }
}