[KnapSack] 백준 1495: 기타리스트

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, S;
    cin >> N >> S >> M;

    vector<int> volume(N);
    for (int i = 0; i < N; i++)
    {
        cin >> volume[i];
    }

    vector<vector<int>> dp(N + 1, vector<int>(M + 1));
    dp[0][S] = 1;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 0; j <= M; j++)
        {
            if (dp[i - 1][j] == 1)
            {
                S = j;
                if (S - volume[i - 1] >= 0)
                {
                    dp[i][S - volume[i - 1]] = 1;
                }
                if (S + volume[i - 1] <= M)
                {
                    dp[i][S + volume[i - 1]] = 1;
                }
            }
        }
    }

    for (int i = M; i >= 0; i--)
    {
        if (dp[N][i] == 1)
        {
            cout << i;
            return 0;
        }
    }

    cout << -1;
}

1495번: 기타리스트 (acmicpc.net)

1495번: 기타리스트

 

1. 곡 수 N은 최대 50개고, 곡이 넘어갈 때마다 필수적으로 볼륨을 늘리거나 줄여야 하므로, 모든 경우의 수는 2^50가지나 되어서 모든 경우의 수를 다 세어보기에는 너무 많다.

 

2. 그래서 dp[곡][음량] 배열을 만들고, 다음 곡으로 넘어갈 때마다 이전 볼륨을 가져와서, volume 배열의 값을 더하거나 뺀 값이 0과 최대값 사이에 위치하는지 확인한 후, 만일 적정 범주에 있다면 dp[현재곡][음량] 을 1로 해 준다.

 

3. 마지막 음악의 최대 볼륨을 구하는 문제이므로, dp[마지막곡][i] == 1이 되는 곡 중 가장 큰 값 i 를 출력하면 된다.

 

이렇게 1. bruteforce로 하기에는 너무 많고 2. 선택 할 수 있는 용량이 제한되어 있는 경우에 돌리는 dp 알고리즘을 knapsack, 가방싸기라고 부른다고 한다. 솔직히 나도 오늘 처음 알게 된 개념이라 아직 설명하기가 부족한데, 이게 맞는 건지 모르겠다. 아무튼 일단 공부하면서 올리는 포스팅이니까 다른 knapsack 문제들을 몇 개 더 풀면서 구체화해 나가야겠다.