[BOJ] 1495번_기타리스트_DP (C++)

[문제]

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

공연에서 N개의 곡을 연주하려고 한다. 이번 공연에서는 특별히 매번 곡이 시작하기 전에 볼륨을 바꿀 예정이다.

먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V[]라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번째 곡은 P+V[i]나 P-V[i]의 볼륨으로 연주해야한다. 하지만, 0보다 작거나, M보다 큰 볼륨으로 연주할 수는 없다.

곡의 개수 N, 시작 볼륨 S, 한계 볼륨 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하는 문제이다.

[사용 알고리즘]

DP(다이나믹 프로그래밍)

[풀이 핵심]

• 이 문제는 이중배열을 사용하면 쉽게 해결할 수 있다. dp[x][y]라는 이중배열에 x번째 곡을 y볼륨으로 연주할 수 있는지 저장해가며 하위 답을 통해서 결과를 도출하면 된다.
• 시작부터 생각해보면, 시작볼륨에서 v[1]의 볼륨을 더한 값이 M을 넘지않으면 dp[1]S+v[1]]이 true가 되는 것이고, 시작볼륨에서 v[1]의 볼륨을 뺀 값이 0을 넘으면 dp[1]S-v[1]]이 true가 되는 것이다. 다음으로 2번째 곡을 연주할 때는 첫번째 곡을 연주한 볼륨에서 v[2]의 볼륨 값을 더한 값이 M을 넘지않으면 dp[2]첫번째 곡을 연주한 볼륨 + v[2]]가 true가 되는 것이고, 첫번째 곡을 연주한 볼륨에서 v[2] 값을 뺀 값이 0을 넘으면 dp[2]첫번째 곡을 연주한 볼륨 - v[2]]가 true가 되는 것이다. 이런 식으로 마지막 곡까지 처리해주면 dp[N][x]가 마지막곡에서 나올 수 있는 볼륨들이다. 여기서 x의 최대값을 구하면 정답이된다.

[코드]

//boj1495번_기타리스트_dp

#include<iostream>

using namespace std;

bool dp[51][1001];
int v[51];

int main() {
	int N, S, M;
	cin >> N >> S >> M;

	for (int i = 1; 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]) {
				if (j + v[i] <= M) {
					dp[i][j + v[i]] = true;
				}
				if (j - v[i] >= 0) {
					dp[i][j - v[i]] = true;
				}
			}
		}
	}

	for (int i = M; i >= 0; i--) {
		if (dp[N][i]) {
			cout << i;
			return 0;
		}
	}

	cout << -1;

	return 0;
}