728x90
1495번: 기타리스트
첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.
www.acmicpc.net
#include <iostream>
#include<cstring>
using namespace std;
int main() {
int v[100];
bool dp[101][1001];
int n, s, m;
memset(dp, false, sizeof(dp));
cin >> n >> s >> m;
for (int i = 0; i < n; i++) {
cin >> v[i];
}
dp[0][s] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (dp[i - 1][j] == true) {
int res = j + v[i - 1];
if (res <= m) {
dp[i][res] = true;
}
res = j - v[i - 1];
if (res >= 0) {
dp[i][res] = true;
}
}
}
}
for (int i = m; i >= 0; i--) {
if (dp[n][i] == true) {
cout << i << endl;
return 0;
}
}
cout << -1 << endl;
return 0;
}- dp 배열의 x축은 몇번째 곡인지, y축은 가능한 볼륨 (0~m) 을 나타내고 가능한 볼륨을 true 값을 넣어준다.
- 결과적으로 n번째곡에서 가능한 볼륨중 가장 큰것을 찾으면 된다.