์ด ๋ฌธ์ ๋ ์์ฃผ ํ๋ฒํ ๋ฐฐ๋ญ์ ๊ดํ ๋ฌธ์ ์ด๋ค.
ํ ๋ฌ ํ๋ฉด ๊ตญ๊ฐ์ ๋ถ๋ฆ์ ๋ฐ๊ฒ ๋๋ ์ค์๋ ์ฌํ์ ๊ฐ๋ ค๊ณ ํ๋ค. ์ธ์๊ณผ์ ๋จ์ ์ ์ฌํผํ๋ฉฐ ์ต๋ํ ์ฆ๊ธฐ๊ธฐ ์ํ ์ฌํ์ด๊ธฐ ๋๋ฌธ์, ๊ฐ์ง๊ณ ๋ค๋ ๋ฐฐ๋ญ ๋ํ ์ต๋ํ ๊ฐ์น ์๊ฒ ์ธ๋ ค๊ณ ํ๋ค.
์ค์๊ฐ ์ฌํ์ ํ์ํ๋ค๊ณ ์๊ฐํ๋ N๊ฐ์ ๋ฌผ๊ฑด์ด ์๋ค. ๊ฐ ๋ฌผ๊ฑด์ ๋ฌด๊ฒ W์ ๊ฐ์น V๋ฅผ ๊ฐ์ง๋๋ฐ, ํด๋น ๋ฌผ๊ฑด์ ๋ฐฐ๋ญ์ ๋ฃ์ด์ ๊ฐ๋ฉด ์ค์๊ฐ V๋งํผ ์ฆ๊ธธ ์ ์๋ค. ์์ง ํ๊ตฐ์ ํด๋ณธ ์ ์ด ์๋ ์ค์๋ ์ต๋ K๋งํผ์ ๋ฌด๊ฒ๋ง์ ๋ฃ์ ์ ์๋ ๋ฐฐ๋ญ๋ง ๋ค๊ณ ๋ค๋ ์ ์๋ค. ์ค์๊ฐ ์ต๋ํ ์ฆ๊ฑฐ์ด ์ฌํ์ ํ๊ธฐ ์ํด ๋ฐฐ๋ญ์ ๋ฃ์ ์ ์๋ ๋ฌผ๊ฑด๋ค์ ๊ฐ์น์ ์ต๋๊ฐ์ ์๋ ค์ฃผ์.
์ฒซ ์ค์ ๋ฌผํ์ ์ N(1 โค N โค 100)๊ณผ ์ค์๊ฐ ๋ฒํธ ์ ์๋ ๋ฌด๊ฒ K(1 โค K โค 100,000)๊ฐ ์ฃผ์ด์ง๋ค. ๋ ๋ฒ์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ๊ฑฐ์ณ ๊ฐ ๋ฌผ๊ฑด์ ๋ฌด๊ฒ W(1 โค W โค 100,000)์ ํด๋น ๋ฌผ๊ฑด์ ๊ฐ์น V(0 โค V โค 1,000)๊ฐ ์ฃผ์ด์ง๋ค.
์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ๋ชจ๋ ์๋ ์ ์์ด๋ค.
ํ ์ค์ ๋ฐฐ๋ญ์ ๋ฃ์ ์ ์๋ ๋ฌผ๊ฑด๋ค์ ๊ฐ์นํฉ์ ์ต๋๊ฐ์ ์ถ๋ ฅํ๋ค.
4๊ฐ์ ๋ฌผ๊ฑด, 7kg๊น์ง ๋ฒํธ ์ ์๋ ์ํฉ
๋ฌผ๊ฑด 1 6kg / 13์ ๊ฐ์น
๋ฌผ๊ฑด 2 4kg / 8์ ๊ฐ์น
๋ฌผ๊ฑด 3 3kg / 6์ ๊ฐ์น
๋ฌผ๊ฑด 4 5kg / 12์ ๊ฐ์น
using System;
namespace Baekjoon_Algorithm
{
class Program
{
static void Main()
{
//์ฒซ๋ฒ ์งธ ์
๋ ฅ ๊ฐ(๋ฌผํ์ ์ N๊ฐ, ๋ฒํธ์ ์๋ ๋ฌด๊ฒ K)
int N;
int K;
int[] W;//๋ฌผ๊ฑด์ ๋ฌด๊ฒ ๋ฐฐ์ด
int[] V;//๋ฌผ๊ฑด์ ๊ฐ์น ๋ฐฐ์ด
int[,] DP;//DP ๋ฐฐ์ด
N = int.Parse(Console.ReadLine());
K = int.Parse(Console.ReadLine());
W = new int[N + 1];
V = new int[N + 1];
DP = new int[N+1, K+1];//DP ๋ฐฐ์ด
//๋ฌผํ์ ์ ๋งํผ ๊ฐ์น ์
๋ ฅ
for (int i = 1; i <= N; i++)
{
W[i] = int.Parse(Console.ReadLine());
V[i] = int.Parse(Console.ReadLine());
}
//K๋ฅผ ๋์ง ์์ผ๋ฉด์ ์ต๋์ ๊ฐ์น ๊ฐ์ ๊ฐ์ง ๊ฒฝ์ฐ ์ถ๋ ฅ
for (int i = 1; i <= N; i++)
{
//๋ฌด๊ฒ๋งํผ (1, 7) ๋๋ฉด์
for (int j = 1; j <= K; j++)
{
if(j-W[i] >= 0)//ํ์ฌ ๋ฌด๊ฒ์์ ๊ฐ์ง๊ณ ์๋ ๋ฌด๊ฒ ๋บ์ ๊ฒฝ์ฐ์๋ ๋จ๋ ๋ฌด๊ฒ๊ฐ ์์ผ๋ฉด
{
//์ด์ ๋ฌผ๊ฑด์ ๊ฐ์ ๋ฌด๊ฒ์ ๊ฐ์น์ ๋จ์ ๋ฌด๊ฒ์ ๊ฐ์น ์ค์ ์ต๋๊ฐ
if (Math.Max(DP[i - 1, j], DP[i - 1, j - W[i]] + V[i]) > int.MaxValue) DP[i, j] = 0;
else
{
DP[i, j] = Math.Max(DP[i - 1, j], DP[i - 1, j - W[i]] + V[i]);
}
}
}
}
Console.WriteLine($"MAX:{DP[N, K]}");
}
}
}