백준 / BOJ / 5557 1학년 C++

www.acmicpc.net/problem/5557

5557번: 1학년

 

단순히 계산하면 n개의 숫자 사이에 n-2 개의 +, - 가 존재합니다. (마지막 부호는 = ) 그러므로 $O(2^n)$ 이지만 n=100이므로 시간초과가 날 게 뻔해보입니다. 

그러므로 DP를 이용해 봅시다. 

 

상근이는 0~20까지의 숫자만 알고 있으므로 possible 배열을 이용하여 0~20에 다음 숫자를 계산했을 때 가능하면 dp 경우를 더해줍니다. 그 값을 dp배열에 복사하여 dp배열 내에서 0보다 큰 값이면 해당 숫자의 경우가 가능한 것이므로 이를 반복합니다.

그리고 마지막에서 두번째 수와 계산했을 때 맨 마지막 수가 나오는지 체크하면 됩니다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long ll;

int n;
vector<int>number;
ll dp[21];
ll possible[21]; 
ll res = 0;

void make_number()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		number.push_back(a);
	}
}

int main()
{
	make_number();
	memset(dp, 0, sizeof(dp));
	
	dp[number[0]] = 1;

	for (int i = 1; i < n - 2; i++) {

		int num = number[i];

		memset(possible, 0, sizeof(possible));
		for (int j = 0; j < 21; j++) {

			if (dp[j] > 0) {

				if ((j + num >= 0) && (j + num <= 20)) {
					possible[j + num] += dp[j];
				}
				if ((j - num >= 0) && (j - num <= 20)) {
					possible[j - num] += dp[j];
				}
			}
		}
		memcpy(dp, possible, sizeof(dp));
	}

	int final_num = number[n - 2];
	int result_num = number[n - 1];

	for (int i = 0; i < 21; i++) {
		if (dp[i] > 0) {
			if (i + final_num == result_num)
				res += dp[i];
			if (i - final_num == result_num)
				res += dp[i];
		}
	}

	cout << res;
}