1495 기타리스트

1. 문제

2. 코드

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int N, S, M;
int vol[101];
int dp[101][1001];
 
int maxVal();
 
int main() {
    scanf("%d %d %d", &N, &S, &M);
    for (int i = 1; i <= N; i++)
        scanf("%d", &vol[i]);
 
    if (S + vol[1] <= M)
        dp[1][S + vol[1]] = 1;
    if (S - vol[1] >= 0)
        dp[1][S - vol[1]] = 1;
 
    for (int i = 2; i <= N; i++) {
        int curVol = vol[i];
        for (int j = 0; j <= M; j++) {
            if (dp[i - 1][j] == 1) {
                if (j + curVol <= M)
                    dp[i][j + curVol] = 1;
                if (j - curVol >= 0)
                    dp[i][j - curVol] = 1;
            }
        }
    }
    printf("%d", maxVal());
}
 
int maxVal() {
    for (int i = M; i >= 0; i--) {
        if (dp[N][i] == 1) {
            return i;
        }
    }
    return -1;
}

3. 후기

초기 볼륨은 5이고 다음 볼륨은 5이므로 변경가능한 다음 볼륨은 0, 10 이다.

DP배열을 1로 바꾸고, 다음 볼륨을 구할 때는 전 볼륨이 1인 구간에서 최소값과 최대값사이의 값의 배열을 1로 바꿔준다. 

출처 - https://m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=221078781781&proxyReferer=https%3A%2F%2Fwww.google.com%2F