백준(boj)5557 - 1학년

문제 링크 - https://www.acmicpc.net/problem/5557

👀문제이해 및 풀이방법

DP문제이다 DP문제는 점화식을 정의하는 아이디어가 떠오르지 않으면 진짜 풀어지지가 않는다
이걸 제대로 느낀 문제인데 2차원 배열로 dp를 정의하여 dp[a][b] = a번째 수까지 사용하여 b를 만드는 가지의 개수 이것만 정의된다면 정말 5분만에 짜서 바로 통과했다 이걸 생각해내기가 너무 어려웠다 dp는 정말 수많은 연습만이 살길인것 같다..
따라서 dp[a][b]=dp[a-1][b-arr[a]]+dp[a-1][b+arr[a]]이다.. 물론 b가 20이넘거나 0보다작은 경우 예외처리 해주면 된다

📝코드

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
class first{
private:
    vector<int> arr;
    vector<vector<ll>> dp;
    int N;
public:
    first(){
        std::cin >>N;
        dp.resize(N,vector<ll>(21));
        set_val();
    }
    void set_val(){
        int a;
        for(int i=0;i<N;i++){
            std::cin >>a ;
            arr.push_back(a);
        }
        dp[0][arr[0]]=1;
    }
    ll DP(int a,int b){
        if(a<0 || b>20 || b<0)
            return 0;
        if(dp[a][b])
            return dp[a][b];
        dp[a][b]=DP(a-1,b+arr[a])+DP(a-1,b-arr[a]);
        return dp[a][b];
    }
    void find_sol(){
        std::cout << DP(N-2,arr[N-1]) <<'\n';
    }
};
int main(){
    first ft;
    ft.find_sol();
    return 0;
}