[BOJ] 1495 : 기타리스트 - travelbeeee

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

---

[ 알고리즘풀이 ]

2차원 배열을 이용해서 문제를 해결할 수 있습니다.

dp[x][y] : x 번 째 노래에서 볼륨 y가 가능한지 불가능한지.

dp[0][S] = true 로 시작해서, dp[i - 1][j] 가 true라면 지금 노래의 볼륨을 더하고 빼줘서 dp[i][something] 에 check 해줍니다.

// Volume이 0이 되도 마지막 곡을 연주할 수 없다고 생각해서 겁나게 틀렸습니다.... 문제를 잘읽자!

#include<iostream>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, S, M, t;
	bool check[101][1001] = {};

	cin >> N >> S >> M;
	check[0][S] = true;

	for (int i = 1; i <= N; i++) {
		cin >> t;
		for(int j = 0; j <= M; j++)
			if (check[i - 1][j]) {
				if (j + t <= M)
					check[i][j + t] = true;
				if (j - t >= 0)
					check[i][j - t] = true;
			}
	}
	int ans = -1;
	for (int j = 0; j <= M; j++)
		if (check[N][j])
			ans = j;
	cout << ans;
}

---