[DP] BOJ 5557 1학년

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

5557번: 1학년

 

문제 해결 알고리즘

 

다이나믹 프로그래밍을 활용해서 풀어주는 문제 

 

배열에 0부터 20까지 두고 첫번 째 수부터 그 안에 속하는 등식이면 배열에서 그 해당하는 값의 개수를 더해주면서 동적계획을 해준다.

 

소스 코드

 

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

int N;
long long arr[103], dp[21][103];
long long result = 0;

int main(){
    cin >> N;

    for(int i=0;i<N;i++){
        cin >> arr[i];
    }

    dp[arr[0]][0] = 1;

    for(int i=0;i<N;i++){
        for(int j=0;j<=20;j++){
            if(dp[j][i] != 0){
                if(0<=arr[i+1]+j && arr[i+1]+j<=20){
                    dp[arr[i+1]+j][i+1] += dp[j][i];
                }
                if(0<=j-arr[i+1] && j-arr[i+1]<=20){
                   dp[j-arr[i+1]][i+1] += dp[j][i];
                }
            }
        }
    }
	
    cout << dp[arr[N-1]][N-2];
}