[Algorithm]Baekjoon 1495번 : 기타리스트

https://www.acmicpc.net/problem/1495

1495번: 기타리스트

 
 
int n, s, m;
int v[51] = { 0 };
bool dp[51][1001] = { false };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> s >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> v[i];
    }
 
    if (s - v[1] >= 0) dp[1][s - v[1]] = true;
    if (s + v[1] <= m) dp[1][s + v[1]] = true;
 
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 0; j <= m; ++j)
        {
            if (dp[i-1][j])
            {
                if (j - v[i] >= 0)
                {
                    dp[i][j - v[i]] = true;
                }
 
                if (j + v[i] <= m)
                {
                    dp[i][j + v[i]] = true;
                }
            }
        }
    }
 
    for (int i = m; i >= 0; --i)
    {
        if (dp[n][i])
        {
            cout << i;
            return 0;
        }
    }
 
    cout << -1;
}

 

접해보지 못했던 유형이라서 풀어보길 잘한 문제

사운드를 -할것인가 +할것인가에 따라서 많은 경우의 수가 나오는데, 그 값들을 계속 들고있어야 한다.

무조건 최대값으로만 들고있으면 안된다. m값을 넘으면 안되기 때문에, 작은값을 들고있다가 n번차례때 볼륨값을 +해서 큰값으로 뻥튀기시켜버릴 수 있기 때문이다.

 

그래서 dp테이블을 최대 bool dp[n][m]의 크기로 들고 있어야 한다.

m의 인덱스가 곧 볼륨을 의미하며, 예를들어 dp[3][245] == true일 경우, 3번째까지의 볼륨조절단계에서 볼륨이 245인경우의 수가 존재한다는 것을 의미한다. 

그래서 이전단계 (i-1)에서 true인 값들, 즉 이전단계까지 만들었던 모든 볼륨의 경우의수에다가 현재단계의 볼륨값을 더하거나 빼서 해당값이 올바를경우(이전 볼륨값에서 현재 조절볼륨값을 뺐을 때 0이상이여야하고, 더했을 때 m값이하여야하는), dp테이블에 업데이트한다.

 

업데이트를 전부 마치고 마지막에 dp테이블의 n번째에서 m값부터 0까지 순회하는 반복문에서 처음 만나는 true값에 해당하는 i값을 출력해주면 된다. (제일큰값부터 순회하니까)

n번째에 true값이 한개도 없을경우 -1을 출력하면 된다.