[백준] 7579 - 앱

1. 문제

7579번: 앱

2. 개요

N개의 앱이 있다. 이들을 비활성화시켜 M 이상의 메모리를 확보하려고 한다.

앱들의 현 사용중 메모리와 비활성화시 비용들이 각각 주어졌을 때,

M이상의 메모리를 확보하기 위한 최소 비용을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

일반적인 배낭 문제는 최대 가치를 구하는 문제지만, 이 문제에서 요구하는 것은 최소 비용이라 조금 헤맸다.

일반적인 배낭 문제는 M으로 배낭의 무게가 주어지는데, 여기서는 활용 가능한 최대 비용을 이처럼 활용한다. 현재 모든 앱들이 실행중이라고 할 때의 합계 비용을 이로 활용하는 것이다.

즉 dp[i][j] = i번 째 물건에서 j까지의 비용을 들였을 때의 메모리 해제 값이다.

만약 dp[i][j]가 M이상이라면 비용은 j이므로 이를 출력값과 비교해 나간 후 마지막에 출력해준다.

3-2. Python

import sys

N, M = map(int, sys.stdin.readline().split())

bytes = list(map(int, sys.stdin.readline().split()))
costs = list(map(int, sys.stdin.readline().split()))

total = sum(costs)
answer = total
dp = [[0 for i in range(total + 1)] for j in range(N+1)]

for i in range(1, N + 1):
    for j in range(1, total + 1):
        if j >= costs[i-1]:
            dp[i][j] = max(dp[i-1][j], bytes[i-1] + dp[i-1][j - costs[i-1]])

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

        if dp[i][j] >= M:
            answer = min(answer, j)

print(answer)

3-3. C#

namespace boj_7579
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split();
            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);

            int[] bytes = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int[] costs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            int total = costs.Sum();
            int answer = total;

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

            for (int i = 1; i < N + 1; i++)
            {
                for (int j = 1; j < total + 1; j++)
                {
                    if (j >= costs[i - 1])
                    {
                        dp[i, j] = Math.Max(dp[i - 1, j], bytes[i - 1] + dp[i - 1, j - costs[i - 1]]);
                    }
                    else
                    {
                        dp[i, j] = dp[i - 1, j];
                    }

                    if (dp[i, j] >= M)
                    {
                        answer = Math.Min(answer, j);
                    }
                }
            }

            Console.WriteLine(answer);
        }
    }
}