BOJ 5557 - 1학년

www.acmicpc.net/problem/5557

5557번: 1학년

 

이 문제는 DP 를 써야 풀 수 있다.

이 문제에 대한 점화식은 다음과 같다

 

dp[i][j] = k : i 번째 위치에 있는 숫자로 j 가 있을때 (j 의 범위는 0 ~ 20) 가능한 경우의 수 k

 

문제에서 제시한 예제입력1 을 예로 들면

 

11

8 3 2 4 8 7 2 4 0 8 8 

의 경우,

 

첫번째 수 8에 대해서는 

dp[1][8] = 1 이 성립한다 (첫번째 위치에 들어가는 숫자 8은 경우의 수가 딱 한개임)

 

두번째 수 3에 대해서는

dp[2][8+3] += dp[1][8]

dp[2][8-3] += dp[1][8] 이 성립한다

+3 과 -3 이 가능하기 때문이다.

 

이런식으로 쭉 계산을 해주면 답이 나오는데

 

주의할것은 j 의 범위가 0 ~ 20 이므로, 계산을 하면서 20을 넘거나 음수가 되는 경우는 제외시켜야한다.

그리고 경우의 수가 int 범위를 초과하는 경우도 있으므로, long long 타입으로 dp 배열을 선언한다.

 

 

- c++

#include <bits/stdc++.h>
 
#define MAX 101
 
using namespace std;
 
int N;
int arr[MAX];
long long dp[MAX][21]; // dp[i][j] = k : i 번째 위치에 있는 숫자 j (0 ~ 20) 가 나올때 경우의 수 k 
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N;
    for (int i = 1; i <= N; ++i) cin >> arr[i];
    
    dp[1][arr[1]] = 1;
    
    for (int i = 2; i <= N; ++i) {
        for (int j = 0; j <= 20; ++j) {
            if (dp[i - 1][j] != 0) { // 이전 경우의 수가 존재하는 경우
                if (j - arr[i] >= 0) dp[i][j - arr[i]] += dp[i - 1][j]; // 이전수와의 차가 양수일때  
                if (j + arr[i] <= 20) dp[i][j + arr[i]] += dp[i - 1][j]; // 이전수와의 합산이 20 이하일때 
            }
        }
    } 
    
    cout << dp[N - 1][arr[N]];
    
    return 0;
}