[BAEKJOON] 평범한 배낭(12865번 - C#)

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 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 7
6 13
4 8
3 6
5 12

예제 출력

14

저번의 알고리즘 문제 https://jjomnoon-diary.tistory.com/32 와 같이 DP(Dynamic Programing)를 요구하는 문제이다.

[programmers] 가장 큰 정사각형 찾기(Java)

DP의 설명은 아래 포스팅을 참고하면 된다.(추후 추가)

위의 문제와 같이 맵을 그려준다

6, 13
4, 8
3, 6
5, 12
순으로 진행할것이다.

작은것부터 큰것으로 점차 나아가야 하는 문제이므로

최대 weight이 1이고, 짐이 6w에 13v만 있을때.
최대 weight이 2이고, 짐이 6w에 13v만 있을때.
....
최대 weight이 7이고, 짐이 6w에 13v만 있을때.
최대 weight이 1이고, 짐이 6w에 13v, 4w에 8v가 있을때.
최대 weight이 2이고, 짐이 6w에 13v, 4w에 8v가 있을때.
...
최대 weight이 7이고, 짐이 6w에 13v, 4w에 8v가 있을때.
최대 weight이 1이고, 짐이 6w에 13v, 4w에 8v, 3w에 6v가 있을때.
......
최대 weight이 7이고, 짐이 6w에 13v, 4w에 8v, 3w에 6v, 5w에 12v가 있을때.

각 상태의 최대 값을 구할 것이다.

변수는 위와 같다고 가정한다.

첫번째 짐만 있을 때의 값은

int[,] board = new int[n, k];

for (int i = 0; i < n; i++){
    for (int j = 0; j < k; j++){
        if(j + 1 >= array[i, 0]){
        	board[i, j] = array[i, 1];
        }
    }
}

 

array의 무게가 최대 무게(j)보다 작거나 같다면 board[i, j]에는 array의 가치(value)값이 들어가게 된다.

그럼 두번째 짐까지 있었을때의 값은 어떻게 될까?

int[,] board = new int[n, k];

for (int i = 0; i < n; i++){
    for (int j = 0; j < k; j++){
        if(j + 1 >= array[i, 0]){
        	board[i, j] = Math.Max(array[i, 1], i > 0 ? board[i - 1, j] : 0);
        }
    }
}

위와 유사하다.

두가지 경우중 높은 수가 가치가 된다.

1. 내 무게만을 생각했을 때의 가치 (array[i, 0])
2. 내 무게 이전까지의 가치

즉 내 무게의 가치(array[i, 0])와 이전칸의 가치(board[i - 1, j])를 비교하여 더 큰 수를 현재칸에 넣으면 된다.

이번에는 하나를 더 추가해보자.

• (최대 무게 - 내 무게) 의 가치 + 내무게의 가치
• 내 무게 이전까지의 가치

최대무게(j)가 7이고 현재 array[i, 0]이 3일 때

board[ i - 1 , 최대무게(7) - 현재 무게(3) ] + 현재 가치(6) = 8 + 6 = 14

board[ i - 1 , j - array[i, 0] ] + array[i, 1]

그러므로 14가 된다.

 

소스코드

using System;

namespace MyApp // Note: actual namespace depends on the project name.
{
    internal class Program
    {

        static void Main(string[] args)
        {
            int n = 4;
            int k = 7;

            int[,] array = {{6, 13},
                        {3, 6},
                        {4, 8},
                        {5, 12}};

            int[,] board = new int[n, k];

            int answer = 0;

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < k; j++)
                {
                    if (j + 1 >= array[i, 0])
                    {
                        if (i > 0)
                        {
                            board[i, j] = Math.Max(array[i, 1] + (j - array[i, 0] > 0 ? board[i - 1, j - array[i, 0]] : 0), board[i - 1, j]);
                        }
                        else
                        {
                            board[i, j] = array[i, 1];
                        }
                    }
                    else
                    {
                        board[i, j] = i > 0 ? board[i - 1, j] : 0;
                    }
                    Console.Write("[" + i + "," + j + "]=" + board[i, j] + " ");
                }
                Console.WriteLine("");
            }
            Console.WriteLine("answer : " + board[n - 1, k - 1]);

        }
    }
}

i와 j를 0부터 시작하니 쓸데업ㅅ는 삼항연산자가 많아지고,,,, 그래서 다른버전으로도 만들었다.

using System;

namespace MyApp // Note: actual namespace depends on the project name.
{
    internal class Program
    {

        static void Main(string[] args)
        {
            int n = 4;
            int k = 7;

            int[,] array = {{6, 13},
                        {3, 6},
                        {4, 8},
                        {5, 12}};

            int[,] boards = new int[n + 1, k + 1];
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= k; j++)
                {
                    if (j >= array[i - 1, 0])
                    {
                        boards[i, j] = Math.Max(array[i - 1, 1] + (j - array[i - 1, 0] > 0 ? boards[i - 1, j - array[i - 1, 0]] : 0), boards[i - 1, j]);
                    }
                    else
                    {
                        boards[i, j] = boards[i - 1, j];
                    }
                    Console.Write("[" + i + "," + j + "]=" + boards[i, j] + " ");
                }
                Console.WriteLine("");
            }
            Console.WriteLine("answer : " + boards[n, k]);

        }
    }
}

좀더 깔끔한듯,,,

 

코드 두가지 다 정답으로 뜬 것 까지 확인 했다.

 

 

이게 평범한 배낭이라니...

그래도 저번문제는 해설을 보고 풀었지만 이번문제는 방법만 보고 코딩은 내가 했다..

이렇게 점점 나아가겠지..

DP관련문제를 몇개정도 더 풀어보자...

배워도 배워도 끝이 없구나 😭😭😭😭😭

 

포스팅에 오류가 있거나 오타가 있거나 더 효율이 높은 코드를 알고 계신분은 댓글로 알려주시기 바랍니다.

도움이 되셨다면 공감버튼을 눌러주세요.🥰

 

 

 

 

참고 : https://suri78.tistory.com/2

많은 도움이 됐습니다.