[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을 반환한다. 

 

 

#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; }