백준5557 1학년

작성일 | In

문제 링크

  • http://icpc.me/5557

문제 출처

  • 2011 JOI 예선 4번

사용 알고리즘

  • DP

시간복잡도

  • O(n)

풀이

완전탐색으로 모든 경우를 계산하면 O(2n)이 나오기 때문에 최적화를 합시다.

dp[i][j] = i번 인덱스까지의 연산 결과가 j인 경우의 수로 정의하고 점화식을 채워줍시다.
연산 도중 0보다 작거나 20보다 커질 수는 없으니 dp table의 크기를 dp[101][21]정도로만 선언하면 됩니다.

상태 공간은 n*21, 각 상태마다 O(1)에 계산할 수 있으므로 O(n)만에 답을 구할 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

vector<int> v;
typedef long long ll;
int n;
ll dp[110][22];

ll f(int i, int j){
    if (i < 0 || j < 0 || j > 20) return 0;
    if (i == 0 && j == v[0]) return 1;
    if (dp[i][j] != -1) return dp[i][j];

    return dp[i][j] = f(i-1, j-v[i]) + f(i-1, j+v[i]);
}

int main(){
	cin >> n;
	int res;
	v.resize(n);
	for(int i=0; i<n; i++){
		cin >> v[i];
	}
	memset(dp, -1, sizeof(dp));

	cout << f(n-2, v[n-1]);
}