해결법

• 상근이는 0부터 20까지밖에 모르기 때문에, 연산한 결과는 0부터 20까지만 고려하면 된다.
• 그렇다면 0~20까지의 배열에 각 숫자가 나올 수 있는 경우의 수를 저장하면 된다.
  • dp[i][j]는 i번째 숫자까지 연산했을 때, j가 나오는 경우의 수이다.

소스코드

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int n;
int nums[101];
ll dp[101][21];

void solve(){
	//dp[i][j] : i번째 숫자까지 연산한 결과가 j가 되는 경우의 수
	dp[1][nums[1]] = 1; 
	
	for(int i = 2; i<n; i++){
		for(int j = 0; j<=20; j++){
			if(!dp[i-1][j]) continue;
			int plus = j + nums[i];
			int minus = j - nums[i];
			if(plus<=20) dp[i][plus] += dp[i-1][j];
			if(0<=minus) dp[i][minus] += dp[i-1][j];
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i = 1; i<=n; i++){
		int num; cin>>num;
		nums[i] = num;
	}
	solve();
	cout<<dp[n-1][nums[n]];
}

제출결과