[BOJ] 5557. 1학년

*dp[][] 에는 현재 인덱스에서 나온 결과에 따라 경우의 수를 저장한다.

8

3

2

4

8

7

2

4

0

8

8

dp[0][8] = 1 

1. 8+3 == 11 로 0과 20 사이의 수이므로 

dp[1][11] = 1

2. 8-3 == 5 

dp[1][5] = 1

 

이런 식으로 경우의 수를 표시해야 한다. 

 

*하지만 이 경우가 마지막에 부등호가 성립되어야 하기 때문에

부등호가 나와야 하는 직전의 인덱스 (n-1)까지 간 후에 숫자들을 저장하고 있는 num[n-1]의 값과 현재까지 계산한 값이 같다면 1을 반환 / 같지 않다면 0을 반환한다. 

 

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

#include <iostream> #include <vector> #include <algorithm> using namespace std;   typedef unsigned long long ll; int n; int num[101]; bool visited[101]; ll dp[101][21]; //계산 후 나오는 수에 따라 경우의 수를 저장한다.   ll dfs(int idx, int res) {           if (idx == n - 1) {         if (res == num[n - 1]) return 1;         else return 0;     }       if (dp[idx][res]) return dp[idx][res];       ll& ret = dp[idx][res];       if (res - num[idx] >= 0) {         ret += dfs(idx + 1, res - num[idx]);     }     if (res + num[idx] <= 20) ret += dfs(idx + 1, res + num[idx]);       return ret; } int main() {       ios_base::sync_with_stdio(0);     cin.tie(0);       cin >> n;       for (int i = 0; i < n; i++) {         cin >> num[i];     }       dp[0][num[0]] = 1;     cout << dfs(1, num[0]) << '\n';       return 0; }