1495번: 기타리스트

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


$O(nm)$

ck[i][j]: i번 곡까지 보았을 때 j 볼륨이 가능한지 여부
이를 채우고 n번 곡까지 보았을 때 가능한 최대 볼륨을 출력한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, s, m, ck[101][1001], i, x;
int main() {
    scanf("%d %d %d", &n, &s, &m);
    ck[0][s] = 1;
    for (i = 0; i < n; i++) {
        scanf("%d", &x);
        for (int j = 0; j <= m; j++) {
            if (!ck[i][j]) continue;
            if (j >= x) ck[i + 1][j - x] = 1;
            if (j + x <= m) ck[i + 1][j + x] = 1;
        }
    }
    for (i = m; i >= 0; i--) if (ck[n][i]) break;
    printf("%d", i);
    return 0;
}