[C++]백준 5557번: 1학년

문제 출처

풀이

전형적인 DP문제였다. 앞에서부터 계산하기보다는 뒤에서부터 계산해나가는 것이 편해보였다. 이 문제가 DP로서 풀리는 이유는 0부터 20까지의 제한 덕분인데 이것이 없었다면 계산복잡도가 엄청났을 것이다. 수의 제한이 0부터 20까지이기 때문에 우리는 dp[N][21]짜리 2차원 vector로 계산이 가능해졌다. 전체코드는 다음과 같다

#include<iostream>
#include<vector>

using namespace std;

void Dp(vector<vector<long long>> &dp , int i , vector<int> &arr) {
	for ( int t = 0; t < 21; t++ ) {
		int k1,k2;
		if ( dp[i + 1][t] > 0 ) {
        	//arr[i]값과 더해지거나 빼져서 나올 수 있는 t값을
            //계산한다. 이 때 범위 제한이 0부터 20까지기 때문에 계산이 가능하다.
			k1 = t - arr[i];
			k2 = t + arr[i];
			if ( k1 >= 0 )dp[i][k1] += dp[i + 1][t];
			if ( k2 <= 20 )dp[i][k2] += dp[i + 1][t];
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
	int N;
	cin >> N;
	vector<vector<long long>> dp(N, vector<long long>(21,0));
	vector<int> arr(N);
	for ( int i = 0; i < N; i++ ) {
		cin >> arr[i];
	}
    //초기값 계산.
    //arr[N-1]은 등식 우변값이고 arr[N-2]는 등식 좌변의 마지막값이다.
	int t = arr[N - 1] - arr[N - 2];
	if ( t >= 0 )dp[N - 2][t]++;
	t = arr[N - 1] + arr[N - 2];
	if ( t <= 20 )dp[N - 2][t]++;

	for ( int i = N-3; i >= 0; i-- ) {
		Dp(dp, i, arr);
	}
	long long res=0;
    //처음 값은 0에서 arr[0]이 더해지는 것과 동일하므로
    //결과값은 dp[1][arr[0]]에 들어있게 된다.
	res = dp[1][arr[0]];
	cout << res << endl;
	return 0;
}