https://www.acmicpc.net/problem/1495
1495번: 기타리스트
첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.
www.acmicpc.net
이 문제는 다이나믹 프로그래밍 문제이다.
다이나믹 프로그래밍의 본질은, 복잡한 문제를 간단한 여러 문제로 나누어서 해결하는 것이다!
이 문제는, 마지막 곡의 볼륨의 최댓값을 나타내는 것이다.
다이나믹 프로그래밍에서는 점화식을 찾는 것이 중요하다. 그 점화식은 항상 성립해야 한다.
점화식을 찾는 것이 간단한 여러 문제로 나누어서 푸는 것의 핵심이다.
i번째 곡의 볼륨의 최댓값을 찾아보자. i - 1번째 곡의 볼륨의 최댓값을 이용할 것이다.
DP(i) = max(DP(i - 1) + V[i], DP(i - 1) - V[i])
(DP(i - 1) + V[i] <= M && DP(i - 1) - V[i] >= 0)
하지만 이렇게 풀면 되지 않는다. i - 1번째 곡의 볼륨의 최댓값이 i번째 곡의 볼륨의 최댓값은 아니다...
i번째 곡의 볼륨의 최댓값을 구하기 위해서, i - 1번째 곡의 볼륨의 모든 값을 봐야 한다.
이번 문제는 For문을 통해서는 값을 찾을 순 없고, 함수를 재귀적으로 호출하면서, 메모이제이션도 동시해 수행할 것이다.
해설코드(C++).
#include <cstring>
#include <iostream>
#define MIN -987654321
using namespace std;
int N, S, M;
int answer = -1;
int arr[101];
int dp[101][1001];
int func(int cnt, int sound){
if(dp[cnt][sound] != -1)
return dp[cnt][sound];
if(cnt == N + 1)
return sound;
dp[cnt][sound] = MIN;
if(sound + arr[cnt + 1] <= M)
dp[cnt][sound] = func(cnt + 1, sound + arr[cnt + 1]);
else
dp[cnt][sound] = MIN;
if(sound - arr[cnt + 1] >= 0)
dp[cnt][sound] = max(dp[cnt][sound], func(cnt + 1, sound - arr[cnt + 1]));
return dp[cnt][sound];
}
int main() {
cin >> N >> S >> M;
for(int i = 1; i <= N ; i++)
cin >> arr[i];
memset(dp, -1, sizeof(dp));
answer = func(0, S);
if(answer == MIN)
cout << -1 << endl;
else
cout << answer << endl;
return 0;
}