백준 1495 기타리스트(c++)

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

1495번: 기타리스트

문제에서 주어지는 입력은 N(연주할 곡), S(시작 볼륨), M(최대 볼륨)입니다. 

두 번째 입력에서는 연주할 곡의 볼륨입니다. 연주는 P-V[i], P+V[i]의 볼륨으로만 연주해야 하고, 구하고자 하는 결과는 마지막 곡을 연주했을 때의 볼륨의 최댓값입니다. 

 D[i][j]는 i번 곡을 j로 연주할 수 있으면 true, 그렇지 않으면 false를 반환합니다.  지속적으로 검사하고, d[n][i] 값이 true이면 최댓값 i로 갱신해 주면 끝입니다.

 

<코드>

#include <cstdio> // 입출력 속도향상을 위해 다음 헤더 이용
#include <cstring>

int n, s, m;
int a[101];
bool d[101][1001];

// s-> s+v[i], s-v[i] -> s+v[1]+v[2], s+v[1]-v[2], s-v[1]+v[2], s-v[1]-v[2]
// D[i][j] = i번 곡을 볼륨 j로 연주할 수 있으면 1, 없으면 0

int main()
{
    scanf("%d %d %d", &n, &s, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    memset(d,false,sizeof(d));
    d[0][s] = true;

    for (int i = 0; i <= n - 1; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            if (!d[i][j])
                continue;
            if (j - a[i + 1] >= 0)
                d[i + 1][j - a[i + 1]] = true;
            if (j + a[i + 1] <= m)
                d[i + 1][j + a[i + 1]] = true;
        }
    }
    int ans = -1;
    for (int i = 0; i <= m; i++)
    {
        if (d[n][i])
            ans = i;
    }
    printf("%d\n", ans);
}