[BOJ/C++] 백준 1495 - 기타리스트

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

1495번: 기타리스트

마지막곡을 연주할 때 k인 볼륨을 설정하는 것이 가능한지 ? 를 기준으로 문제를 풀 수 있게 다이나믹 프로그래밍 알고리즘을 적용해보았다.

dp(n, k) = max(sol(n-1, k - v[n]),sol(n-1, k+v[n]))

코드는 위와 같다. 둘 중에 하나라도 가능하면 dp[n][k], 즉 k 크기의 볼륨으로 n번째 곡을 연주할 수 있으므로 첫 번째 곡까지 역주행하는 방식으로 점화식을 세웠다. 각 곡에서 v[i]의 크기만큼 볼륨을 키우거나 줄일 수 있으므로, 볼륨을 키울 때는 m보다 작게, 볼륨을 줄일 때는 0보다 큰 경우에만 값을 구할 수 있도록 하였다. 

 

다이나믹 프로그래밍에서 "모르는 것"이라는 조건은 중요하다. 여기에서는 마지막 곡에서 가장 큰 볼륨 K가 궁금한 것이므로, 가능한 최대 크기 M에서부터 시작해서 차례로 내려가며 dp[n][k]에서 dp[1][s]까지 도달이 가능한지 를 재귀함수를 이용하여 풀었다.

 

예를 들어, sol(3,10) 를 호출한다면 v[3] = 7이기 때문에 연쇄적으로 sol(2,3), sol(2, 17)가 호출될 것이다. 이때 dp(2, 17)은 m = 10보다 크기가 크므로 호출되지 않고, sol(2, 3) 만 호출되어 다음 과정을 수행한다. 

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

int n, s, m; 
int dp[51][1001]; // i번째 곡을 연주할 때 j 볼륨으로 설정하는 것이 가능하면 1, 가능하지 않으면 0, 아직 검사하지 않았다면 -1
int volume[51]; 

bool solve(int i, int j) {
	if (i == 0) return j == s;
	int& ret = dp[i][j]; 
	if (ret != -1) return ret;

	int m1 = 0, m2 = 0; 
	if (j - volume[i] >= 0)
		m1 = solve(i - 1, j - volume[i]); 
	if (j + volume[i] <= m)
		m2 = solve(i - 1, j + volume[i]); 
	return dp[i][j] = max(m1, m2); 
}

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	memset(dp, -1, sizeof(dp)); 
	cin >> n >> s >> m; 
	for (int i = 1; i <= n; i++)
		cin >> volume[i]; 
	int j;
	bool isPossible = false;
	for (j = m; j >= 0; j--) {
		if (solve(n, j) == 1) {
			isPossible = true;
			break;
		}
	}
	if (isPossible) cout << j << endl;
	else cout << -1 << endl; 
	return 0; 
}