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

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

1495번: 기타리스트

 

dp 문제다. 처음 문제를 읽고 떠로으는 생각은 bfs였지만 시간복잡도가 대충 O(2^n)이 나와서 시간 초과를 받게 될게 뻔했다. 남은건 dp 뿐이었다. 근데 나는 dp가 너무 어렵다... 아이디어가 생각이 나지 않아 아이디어만 참고했다. 그래서 50점짜리 풀이라고 해야하나....

 

이중 for문으로 풀 수 있는 문제다. 우선 이 문제의 아이디어는 다음과 같다. 

 

n번째 볼륨값은 n-1번째까지 조절한 모든 볼륨에서 n번째 볼륨을 +- 해준 값
n-1번째 볼륨값은 n-2번째까지 조절한 모든 볼륨에서 n-1번째 볼륨을 +- 해준 값
n-2번째 볼륨값은 n-3번째까지 조절한 모든 볼륨에서 n-2번째 볼륨을 +- 해준 값
n-3번째 볼륨값은 n-4번째까지 조절한 모든 볼륨에서 n-3번째 볼륨을 +- 해준 값

...

2번째 볼륨값은 1번째까지 조절한 모든 볼륨에서 2번째 볼륨을 +- 해준 값
1번째 볼륨값은 0번째까지 조절한 모든 볼륨에서 1번째 볼륨을 +- 해준 값

 

dp의 핵심은 dp의 정의와 그 값이 무슨 의미인지 아는 것. 위 아이디어를 기반으로 dp를 정의해보자. dp[i]를 i번째 볼륨값이라고 하자. 모든 볼륨에서 가질 수 있는 볼륨값은 0 ~ m 까지다. 따라서 dp는 아래와 같이 정의될 수 있으며 값의 의미는 다음과 같다.

 

dp[i][j] = 1  // i번째 볼륨 결과값 중 j 존재
dp[i][j] = 0  // i번째 볼륨 결과값 중 j 존재하지  않음

 

이전에 가능한 모든 결과값에 현재 볼륨을 더하거나 빼주면 된다. 이때 0 ~ m 범위를 잊지 말자. 출력값은 마지막 볼륨의 결과값 dp[n]의 배열 안에 있다. dp[n][m] 부터 m을 1씩 감소시키면서 값이 1이면 m을 출력하면 되고, 모든 값이 0이면 가능한 값이 없다는 뜻이므로 -1을 출력하면 된다. 

 

#include <iostream>
using namespace std;

int n, start, m;
int volume[51];
int dp[51][1001]; // dp[i][j] = i번째 볼륨 결과값 중 j 존재하면 1, 아니면 0

int main() {
	cin >> n >> start >> m;
	for (int i = 1; i <= n; i++)
		cin >> volume[i];

	dp[0][start] = 1;

	int change;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			// dp[i - 1][j] = true면 j기준 볼륨조절
			if (dp[i - 1][j]) {
				change = j + volume[i]; // 볼륨 up
				if (change <= m) {
					dp[i][change] = 1;
				}

				change = j - volume[i]; // 볼륨 down
				if (change >= 0) {
					dp[i][change] = 1;
				}
			}
		}
	}

	for (int i = m; i >= 0; i--) {
		if (dp[n][i]) {
			cout << i << endl;
			return 0; // 종료
		}
	}
	
	cout << -1 << endl;

	return 0;
}