[BOJ 5557] 1학년

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

DP문제이다. DP[i][j] 테이블 정의를  i번째 숫자까지 사용하였을 때 j가 나오는 경우의 수로 정의하면 

 dp[i][j] = dp[i-1][j-arr[i]]+dp[i-1][j+arr[i]  가 된다. 물론 조건인 0이상 20 이하를 if문으로 체크해주어야 한다.

 27번째 줄처럼 가장 첫수의 가능 경우를 1로 설정해주어야 한다. 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>
#include <stack>
#define MAX_N 50
#define INF 1e8
 
typedef long long ll;
 
using namespace std;
 
ll n,dp[111][22],arr[111];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(dp,0,sizeof(dp));
    cin >> n;
    
    for(int i=1;i<=n;i++){
        cin >> arr[i];
    }
    dp[1][arr[1]] = 1;
    
    for(int i=1;i<=n;i++){
        for(int j=0;j<=20;j++){
            if(j+arr[i] <=20){
                dp[i][j] += dp[i-1][j+arr[i]];
            }
            if(j-arr[i]>=0){
                dp[i][j] += dp[i-1][j-arr[i]];
            }
        }
    }
    cout << dp[n-1][arr[n]] <<endl;
    return 0;
}

해당 문제의 경우 단순 for문으로도 구현이 가능하고 내가 삽질한 재귀적으로도 접근이 가능하다. 아직은 for와 재귀를 어느dp에 적용해야 효율적일지 판별하는데 많이 삽질을 하는듯하다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>
#include <stack>
#define MAX_N 50
#define INF 1e8
 
typedef long long ll;
 
using namespace std;
 
ll arr[55],dp[55][111],n;
 
 
ll solve(int val ,int pos){
    if(val <0 || val >20)   return 0LL;
    
    if(pos == 2){
        if(val == arr[1])return 1;
        else{
            return 0;
        }
    }
    
    ll &ret = dp[val][pos];
    if(ret != -1)
        return ret;
    
    return ret = solve(val-arr[pos-1] , pos-1) + solve(val+arr[pos-1] , pos-1);
}
 
int main(){
    cin >> n;
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++){
        cin >>arr[i];
    }
    
    cout << solve(arr[n],n) <<endl;
    
    
}

해당처럼 거꾸로 하는 방식을 통하여 2번째까지 사용하였을 때 값이 arr[1]과 같다면 +1을 해주는 방식을 통해서도 해결 가능하다.