(c++)백준 1459번: 기타리스트

www.acmicpc.net/problem/1495

1495번: 기타리스트

[풀이]

DP로 풀 수 있는 문제였다.

DP[i][j] : i번째 곡을 j 볼륨으로 연주 가능한가?(boolean)

점화식

if DP[i][j] AND j+V[i] <= M : DP[i+1][j+V[i]] = true

            AND j-V[i] >= 0 : DP[i+1][j-V[i]] = true

 

#include <iostream>
#include <algorithm>//max
using namespace std;

int N, S, M;
int V[101];
bool DP[101][1001];

void solution() {
	for (int i = 0; i <= N - 1; i++) {
		for (int j = 0; j <= M; j++) {
			if (DP[i][j]) {
				if (j + V[i + 1] <= M)
					DP[i + 1][j + V[i + 1]] = true;
				if (j - V[i + 1] >= 0)
					DP[i + 1][j - V[i + 1]] = true;
			}
		}
	}
	int res = -1;
	for (int i = 0; i <= M; i++) {
		if (DP[N][i])
			res = i;
	}
	cout << res << '\n';
}

int main() {
	cin >> N >> S >> M;
	for (int i = 1; i <= N; i++) {
		cin >> V[i];
	}
	DP[0][S] = true;
	solution();
	return 0;
}