[백준] 1495 기타리스트

백준 1495 기타리스트

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

• 볼륨의 최댓값을 반환하는 함수를 구현한 풀이

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

const int MIN = -1001;

int N, S, M;
int V[100];
int cache[1000][100];

int getMaxVolume(int nowVolume, int i) {
	if (nowVolume > M || nowVolume < 0) return MIN;
	if (i == N) return nowVolume;

	int& ret = cache[nowVolume][i];
	if (ret != -1) return ret;

	return ret = max(getMaxVolume(nowVolume + V[i], i+1), getMaxVolume(nowVolume - V[i], i + 1));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	for(int i = 0; i<1000; ++i)
		memset(cache[i], -1, sizeof(cache[i]));
	
	cin >> N >> S >> M;
	for (int i = 0; i < N; ++i)
		cin >> V[i];

	int maxV = getMaxVolume(S, 0);
	if (maxV == MIN) cout << -1;
	else cout << maxV;

	return 0;
}

• 볼륨의 변화량의 최댓값을 반환하는 함수를 구현한 풀이

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

const int MIN = - 1001;

int N, S, M;
int V[100];
int cache[100][1000];

//i번째 곡을 연주하기 전~마지막 곡을 연주할 때 까지 볼륨의 변화의 최대값
int getVolumeChange(int i, int sumOfVolumeChange) {
	//base case
	if (sumOfVolumeChange > (M-S)) return MIN;
	if (sumOfVolumeChange < (0-S)) return MIN;
	if (i == N) return sumOfVolumeChange;

	//메모이제이션
	int& ret = cache[i][sumOfVolumeChange];
	if (ret != -1) return ret;

	return ret = max(getVolumeChange(i+1, sumOfVolumeChange + V[i]), getVolumeChange(i + 1, sumOfVolumeChange - V[i]));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	for(int i = 0; i<100; ++i)
		memset(cache[i], -1, sizeof(cache[i]));
	
	cin >> N >> S >> M;
	for (int i = 0; i < N; ++i)
		cin >> V[i];

	int volumeChange = getVolumeChange(0, 0);

	if (volumeChange == MIN) cout << -1;
	else cout << S + volumeChange;
	return 0;
}