BOJ 백준 1495 : 기타리스트

시작하면서

　이번 문제는 다이나믹 프로그래밍 문제이다.

BOJ 1495 - 기타리스트

​

문제 이해

​ 해당 문제는 조건을 잘 이해해야한다.

1. 곡의 개수 N의 최대값은 100이다.
2. 볼륨 M의 최대값은 1000이다.
3. 시작 볼륨은 M보다 작다.

​ 만약 조건이 없다고 생각하고 모든 경우의 수를 다 해본다고 가정하면, 한 depth에서 P+V[i], P-V[i] 로 총 2번의 계산이 나오므로 depth의 최대값인 100번을 하게 되면 2^100 이라는 어마어마한 수치가 나오게 된다.

​ 이때 조건을 보면 볼륨은 0보다 밑으로 내려갈 수 없고, 최대값인 1000이상으로는 올라갈 수 없으므로 범위가 상당히 좁다는 것을 알 수 있다. 그래서 매번의 계산마다 겹치는 부분이 많이 생길 것이므로 볼륨의 최대값인 M을 기준으로 계산했는지 여부를 판단하고, 이미 계산한 볼륨 숫자라면 건너뛰는 방식으로 한 depth에서 최대 계산을 1000번으로 줄일 수 있다.

​ 이렇게 줄이면 최대의 계산 값은 100(N의 최대값) * 1000(볼륨의 최대값) = 약 100,000번으로 줄어든다.

​

해결

#include <iostream>
#include <vector>
#include <queue>
#include <math.h>

using namespace std;

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // sync off

    vector<bool> isUsed;
    vector<int> volumes;
    queue<int> q;
    int preQcount = 0;
    int N, S, M;

    cin >> N >> S >> M;

    volumes.resize(N);
    for (int i = 0; i < N; i++)
    {
        cin >> volumes[i];
    }

    // 계산했는지 여부를 판단하는 벡터
    isUsed.resize(M + 1);

    // 시작 볼륨을 넣는다.
    q.push(S);
    preQcount = q.size();

    for (int i = 0; i < N; i++)
    {
        // 이전 뎁스에서 넣은만큼만 계산한다.
        while (preQcount > 0)
        {
            int value = q.front(); q.pop();
            int calculatedValue = 0;
            preQcount--;

            // 볼륨을 높이는 경우
            calculatedValue = value + volumes[i];
            if (calculatedValue <= M && isUsed[calculatedValue] == false)
            {
                isUsed[calculatedValue] = true;
                q.push(calculatedValue);
            }

            // 볼륨을 낮추는 경우
            calculatedValue = value - volumes[i];
            if (calculatedValue >= 0 && isUsed[calculatedValue] == false)
            {
                isUsed[calculatedValue] = true;
                q.push(calculatedValue);
            }
        }

        // 이번 뎁스에서의 큐 사이즈를 다음 뎁스에서 계산하기 위해 저장한다.
        preQcount = q.size();

        // 계산했는지 여부를 판단하는 벡터를 초기화한다.
        isUsed.assign(isUsed.size(), false);
    }

    int result = -1;

    // 마지막 뎁스까지 계산했을때 가장 큰 값을 찾는다.
    while (!q.empty())
    {
        int value = q.front(); q.pop();
        result = max(result, value);
    }

    cout << result;

    return 0;
}

​

마치며

　계산한 부분을 기록해서 반복 계산을 하지 않게 만드는 것도, 다이나믹 프로그래밍의 일부 개념으로 들어갈 수 있는 사실을 알았다.