난 왤케 DP가 어렵지.... DP 풀면 세상 바보가 된 기분이다.. 솔직히 이것도 좀 지저분하게 푼 것 같다... 만약 보신다면 참고용으로만... 다른 문제 python으로 풀다가 너무 느려서 화가 나서 이번에 거의 지지난 학기 이후로 안 만지던 c++로 했는데 알고리즘보다 c++ 문법이 기억 안나서 더 해맨듯 ㅎㅎ;
1. 문제
기타리스트가 N개의 곡을 연주하려고 한다. 근데 각 곡마다 볼륨을 다르게 조절하고 싶단다.그럴 수 있지. 각 곡마다 조절할 수 있는 볼륨 리스트 v가 주어진다. 가령, 현재 볼륨이 p고 i번째 곡을 연주하기 전이라면, i번 곡은 p+v[i] or p-v[i]으로만 할 수 있다. 단 볼륨은 주어진 M을 초과하거나 음수일 수 없다.
2. 어떻게 풀었지?
좀전에 풀었던 문제가 knapsack problem이어서 그런진 몰라도 비슷한 느낌이 난다고 생각했다. 그 때는 dp[물건의 갯수][무게의 범위] 로 풀었으니까, 이번에도 비슷하게 dp[곡 갯수][볼륨의 양] 이런 식으로 비슷하게 풀면 될 것 같다고 생각했다.
요새 dp를 풀 때마다 top-down으로 해야 할 지, bottom-up으로 해야 할 지 잘 모르겠다... 사실 전에 탑 다운으로 파이썬으로 풀면 스택을 넘길 수 있다고 한 것 같아서 이번에 c++로 한건데 결국 bottom-up으로 풀었다; 그냥 파이썬 쓸 걸;
대충 요런 느낌으로 2차원 배열을 쭉쭉 채워서 마지막 n일때의 최댓값을 리턴 했다. 난 dp 풀 때마다 바보가 된 느낌인데 저렇게 쓰고 보니까
- 2차원 배열을 [곡갯수][볼륨의 최대 범위]로 두고 -1로 초기화
- 초기값은 넣어주자. S가 주어지까
if s+v[1] > m 인 경우
if s-v[1] < 0 인 경우
이 둘을 이차원 배열에 세팅 - 이제부터는 걍 2차원 배열 돌면서, -1이 아니면 그 값에 해당하는 인덱스의 값이 현재 들고 있는 값과 지금 내가 바꿔줄 값 비교해서 큰 값 넣어주기. 뭔소리야
ex) 예시에서 주는 값이 s = 5, v= [5,3,7] m = 10이라면
- 첫 번째 연주곡은 값을 정할 수 있음. 5+5 <= 10 . 5-5 >= 0. 따라서 dp[1][0], dp[1][10] 셋팅
- 첫 번째 행부터 반복문 돌면서 -1이 아니면 v[i+1]을 더하거나 빼고 범위 체크 한 후 해당 인덱스 값 세팅
이렇게 하면 어차피 인덱스의 값이 벨류가 되는 것 같아서 좀 별론 것 같은데... 그래서 크게 맘에 안든다..다시 고쳐봐야 할 것 같다.. 답은 맞았으니까 뭐..
3. 어디서 해맸지?
사실상 c++ 문법 다 까먹음; 가끔 이렇게 해야겠다..
2차원 배열 초기화 하는거도 ={-1,} 이렇게 하면 안되더라...
나는 memset으로 했는데 심지어 전체 범위도 잘못 설정해서 계속 에러 떴었다 ㅋㅋㅋ;
4. code
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX_NUM 101
#define MAX_VOLUME 1001
using namespace std;
int v[MAX_NUM];
int dp[MAX_NUM][MAX_VOLUME];
int main() {
int n, s, m;
int max_val = -1;
fill_n(v, MAX_NUM, 0);
for (int i = 0; i < MAX_NUM; i++) {
memset(dp[i], -1, sizeof(int) * MAX_VOLUME);
}
cin >> n >> s >> m;
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
if (s + v[1] <= m) { dp[1][s + v[1]] = s + v[1]; }
if (s - v[1] >= 0) { dp[1][s - v[1]] = s - v[1]; }
for (int i = 1; i <= n-1; i++) {
for (int j = 0; j <= m; j++) {
if (dp[i][j] != -1) {
if (dp[i][j] + v[i + 1] <= m) { dp[i + 1][dp[i][j] + v[i + 1]] = max(dp[i + 1][dp[i][j] + v[i + 1]], dp[i][j] + v[i + 1]); }
if (dp[i][j] - v[i + 1] >= 0) { dp[i + 1][dp[i][j] - v[i + 1]] = max(dp[i + 1][dp[i][j] - v[i + 1]], dp[i][j] - v[i + 1]); }
}
}
}
for (int i = 0; i <= m; i++) {
if (max_val < dp[n][i]) { max_val = dp[n][i]; }
}
cout << max_val;
}풀고 보니까 c같이 짰네..
