[백준 5557] 1학년

문제

백준 5557

유형

• dfs
• DP

풀이

단순 dfs로 풀이하면 시간 복잡도가 O(2^100)이므로 메모이제이션을 섞어서 풀이하여야 한다. 테이블 dp[i][j]를 i번째에서 값이 j일 때의 경우의 수로 설정하였다.

값이 0이상 20이하 일 때만 재귀를 실행하면서 총 경우의 수를 구해준다. 총 경우의 수가 2^63 - 1이하 이므로 long long을 써서 오버플로우를 방지해야 한다.

주의해야 할 점은 첫번째 값은 포함하여 시작해야 한다는 점이다 그렇지 않으면 cnt - arr[0]가 무조건 < 0 이므로 원하지 않는 정답을 받게 된다.

코드

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

int n;
long long dp[101][21];
int arr[101];

long long dfs(int d,int cnt) {
	if (d == n - 1) {
		if (cnt == arr[d]) return 1;
		else return 0;
	}

	long long& ret = dp[d][cnt];
	if (ret != 0) return ret;

	if (cnt + arr[d] <= 20) ret += dfs(d + 1, cnt + arr[d]);
	if (cnt - arr[d] >= 0) ret += dfs(d + 1, cnt - arr[d]);

	return ret;
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];

	cout << dfs(1, arr[0]);


	return 0;
}