[C++] 백준 1495번 기타리스트

다이나믹 프로그래밍 문제입니다.

음악이 시작했을 때 볼륨을 수정해야하며,
볼륨의 크기는 0보다 작으면 안되고 M보다 크면 안됩니다.
이 때 마지막 노래를 시작했을 때 가장 크게 키울 수 있는
볼륨의 높이를 맞추는 문제입니다.

DP[i][j]를 사용해 풀었습니다.
i는 음량 j는 현재 가능한 볼륨과 다음 가능한 볼륨입니다.

현재 가능한 음량에서 이번 노래의 소리를 더하고 뺀것을 DP[i][1]에 넣습니다.
이와 같은 방식을 반복하여 마지막 노래를 계산한 후 
DP배열에 가장 큰 i값에 값이 들어있는 i를 출력해서 문제를 풀었습니다.

#include <iostream>
#include <cstring>
using namespace std;

int sound[1010];
int DP[1010][2];

int main(int argc, char *argv[])
{
	memset(sound, 0, sizeof(sound));
	memset(DP, 0, sizeof(DP));

	int N, S, M;
	cin >> N >> S >> M;

	for (int i = 1; i <= N; ++i) {
		cin >> sound[i];
	}

	DP[S][0] = 1;

	for (int i = 1; i <= N; ++i) {
		for (int j = 0; j <= M; ++j) {
			if (DP[j][0] != 0) {
				if (j - sound[i] >= 0) {
					DP[j - sound[i]][1] = 1;
				}
				if (j + sound[i] <= M) {
					DP[j + sound[i]][1] = 1;
				}
			}
		}
		for (int j = 0; j <= M; ++j) {
			DP[j][0] = DP[j][1];
			DP[j][1] = 0;
		}
	}
	
	for (int i = M; i >= 0; --i) {
		if (DP[i][0] == 1) {
			cout << i << endl;
			break;
		}
		if (i == 0) {
			cout << "-1" << endl;
		}
	}

 	return 0;
}