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

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

 

2차원 dp테이블 dp[n][m]을 이용해서 n에는 현재 곡의 번호, m은 볼륨 정보로 가능한지 가능하지 않은지 여부를 통해 dp테이블을 채우고, 마지막 곡에서 가장 큰 m의 값이 정답이다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, s, m;
	vector<int> volumes;
	int volume;
	int ans = -1;
	cin >> n >> s >> m;
	vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
	dp[0][s] = true;
	volumes.push_back(s);
	for (int i = 0; i < n; i++) {
		cin >> volume;
		volumes.push_back(volume);
	}
	for (int i = 1; i <= n; i++) {
		int currVolume = volumes[i];
		for (int j = 0; j <= m; j++) {
			if (dp[i - 1][j]) {
				if (j + currVolume <= m) {
					dp[i][j + currVolume] = true;
				}
				if (j - currVolume >= 0) {
					dp[i][j - currVolume] = true;
				}
			}
		}
	}
	for (int i = 0; i <= m; i++) {
		if (dp[n][i]) {
			ans = i;
		}
	}
	cout << ans;
};