(C++) - 백준(BOJ) 5557번 : 1학년

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

5557번: 1학년

dp로 해결한 문제였습니다.

 

풀이방법

d[i][j] = +또는 -인 수식을 i개 뽑았을 때 j수를 만드는 경우의 수로 정의합니다.

i를 n-2개 뽑았을 때 j가 마지막 카드에 도달했다면 경우의 수를 1늘려줍니다.

 

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, num[101], d[101][101];

ll dp(int i, int j){  
    if(i > n - 2 || j < 0 || j > 20) return 0;
    if(i == n - 2 && j == num[n-1]) return 1;
    ll &ret = d[i][j];
    if(ret != -1) return ret;
    ret = 0;
    ret = dp(i + 1,j + num[i + 1]) + dp(i+1,j - num[i + 1]);
    return ret;
}

int main(){
    memset(d,-1,sizeof(d));
    cin >> n;
    for(int i = 0; i < n; i++) cin >> num[i];
    cout << dp(0, num[0]);
}