[C#] 백준 12865번 문제풀이

문제번호: 12865

문제명: 평범한 배낭

문제링크: https://www.acmicpc.net/problem/12865

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다

 

오늘은 다이나믹 프로그래밍 문제인 평범한 배낭 문제를 풀었습니다. 물건들의 무게와 가치를 입력받아 가방 무게 한도가 넘지 않는 선에서 최대가치를 구해내는 문제입니다. 2차원 배열인 테이블을 만들어 i,j 이중반복문으로 table[i, j] = Math.Max(table[i - 1, j], table[i - 1, j - w[i - 1]] + v[i - 1] 식과 함께 테이블을 채워나간 후 마지막 테이블의 끝수를 출력하여 정답을 도출하였습니다.

테이블 배열을 시각화한 사진

기본적인 아이디어는 다음과 같습니다.
다음은 정답코드입니다.

public static void Main()
{
    using StreamReader sr = new StreamReader(Console.OpenStandardInput());
    using StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    int[] NK = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
    int n = NK[0];
    int k = NK[1];

    int[] w = new int[n];
    int[] v = new int[n];

    for (int i = 0; i < n; i++)
    {
        int[] input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
        w[i] = input[0];
        v[i] = input[1];
    }

    int[,] table = new int[n + 1, k + 1];

    // i = 고려한 아이템 개수
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            // 현재 아이템 무게보다 작으면 못 담음
            if (j < w[i - 1])
            {
                table[i, j] = table[i - 1, j];
            }
            else
            {
                table[i, j] = Math.Max(
                    table[i - 1, j],                         // 안 담는 경우
                    table[i - 1, j - w[i - 1]] + v[i - 1]   // 담는 경우
                );
            }
        }
    }

    sw.WriteLine(table[n, k]);
}