[백준 1495] 기타리스트 (C++)

문제 링크: www.acmicpc.net/problem/1495

1495번: 기타리스트

1. 주의할 점

- i번째 곡은 p-v[i] or p+v[i]여야 한다(범위가 아니다)

- 최악의 경우 2^100 -> TLE 발생

 

2. 구현

- DFS나 그리디로 구현하면 TLE가 발생할 수도 있다 -> DP로 해결

- N과 M의 범위가 작다 -> 2차 배열을 이용해도 풀 수 있다

- DP[i번째 곡을][이 값으로 연주할 수 있다]: True or False

- 초기에 Result의 값을 -1로 설정한다

- 0번째 곡을 시작 볼륨이라고 하고 1~N번째 곡까지 For문을 통해 DP[][] 배열을 완성한다

- DP[N][] 중에서 True면서 열의 값이 가장 높은 값을 Result에 저장한다

 

#include <iostream>
using namespace std;
int arr[101];
bool dp[101][1001];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, s, maxi, result = -1;
	cin >> n >> s >> maxi;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	dp[0][s] = true;
	for (int i = 0; i < n; i++) {
		int val = arr[i + 1];
		for (int j = maxi; j >= 0; j--) {
			if (dp[i][j]) {
				if (j + val <= maxi)
					dp[i + 1][j + val] = true;
				if (j - val >= 0)
					dp[i + 1][j - val] = true;
			}
		}
		
	}
	for (int i = maxi; i >= 0; i--) {
		if (dp[n][i]) {
			result = i;
			break;
		}
	}
	cout << result;
	return 0;
}