백준 12865번) 평범한 배낭 (Python, C#)

# 코드 (Python)

n, k = map(int,input().split())

dic = {}
for i in range(n) :
    w, v = map(int, input().split())
    dic[i] = (w, v)
    
lst = [[0]*(k+1) for _ in range(n)]

firstTuple = dic[0]
firstW, firstV = firstTuple

for i in range(1,k+1) :
    if firstW <= i :
        lst[0][i] = firstV
    else :
        lst[0][i] = 0
        
for r in range(1,n) :
    weight, value = dic[r]
    for c in range(1, k+1) :
        if weight <= c :
            lst[r][c] = max(lst[r-1][c], value + lst[r-1][c-weight])
        else :
            lst[r][c] = lst[r-1][c]
            
print(lst[-1][-1])

> 핵심적인 아이디어는

# i번째 물품을 포함하지 않은 무게의 최대가치

# i번째 물품의 가치 + 최대무게에서 i번째 물품의 무게를 뺀 나머지 무게에서 얻을 수 있는 최대가치

를 비교하여 2차원 배열을 채우는 것이다.

 

워낙 유명한 문제라 나도 한번에 풀려고 하다가 낭패를 봤다.

차근차근 접근하면 쉽게 점화식 도출도 가능하고 문제 해결도 가능하다.

 

# 문제 해결 참고 https://badassdev.tistory.com/20, https://suri78.tistory.com/2

 

 

# 코드 (C#)

using System;
using System.IO;
namespace WB
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            string[] arr = sr.ReadLine().Split();
            int n = int.Parse(arr[0]), weight = int.Parse(arr[1]);
            int[,] dp = new int[n+1, weight+1];
          
            for (int i = 1; i <= n; i++)
            {
                arr = sr.ReadLine().Split();
              int  w = int.Parse(arr[0]);
               int  value = int.Parse(arr[1]);
                for (int j = 1; j <= weight; j++)
                {
                    if(w<=j)
                    {
                        dp[i, j] = Math.Max(dp[i - 1, j], dp[i - 1, j - w] + value);
                    }
                    else
                    {
                        dp[i, j] = dp[i - 1, j];
                    }

                }
            }
            sw.Write(dp[n,weight]);
            sw.Close();
        }
    }
}

> 확실히 C#이 간단하긴 하다. 오히려 C#은 처음공부해서 그런가 Input 값을 받는 부분이 조금 미숙해서 어렵다.

이후 로직은 동일하다