백준 5557번 - 1학년

https://www.acmicpc.net/problem/5557

DP 문제로 항상 0보다 크거나 같고 20보다 작거나 같은 것이 이 문제의 핵심이다.

점화식을 세울 때, N번째의 경우의 수는 

1)N-1번째에 구한 경우의 수에서 다음 숫자를 더했을 때 20보다 작거나 같고

2)다음 숫자를 뺏을 때 0보다 크거나 같을 때

N-1번째의 경우의 수를 더해주면 N번째의 경우의 수가 나온다.

말이 조금 복잡하지만 소스코드의 점화식을 보면 바로 이해가 될 것이다.

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
 
 
int main(){
    
    int N;
    int arr[101]={0};
    long dp[101][21]={0};
    
    cin>>N;
    for(int i=1;i<=N;i++)
        cin>>arr[i];
    
    dp[1][arr[1]]++;
    for(int i=2;i<N;i++){
        for(int j=0;j<=20;j++){
            if(dp[i-1][j]){
                if(j+arr[i]<=20)   dp[i][j+arr[i]]+=dp[i-1][j];
                if(j-arr[i]>=0)    dp[i][j-arr[i]]+=dp[i-1][j];
            }
        }
    }
 
    cout<<dp[N-1][arr[N]]<<endl;
    return 0;
}