[백준/Baekjoon] 5557 1학년 C++ :: Dynamic Programming

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

5557번: 1학년

---

1. Logic

- 분기가 +, -로 이루어지기 때문에 2개의 재귀를 들어가야한다.

- DP Tabel을 생성할때 처음 인자는 sum의 범위, 두번째 인자는 몇번째 인덱스를 돌고있는지 체크한다.

 

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;

vector<int> vec;

long long dp[30][101];


long long solve(int sum, int cnt) {
    if (cnt == n - 1 && sum == vec[n - 1]) {
        return 1;
    }
    else if(cnt == n - 1 && sum != vec[n - 1])
        return 0;

    if(sum > 20 || sum < 0) return 0;

    long long &ret = dp[sum][cnt];
    if(ret != -1) return ret;
    ret = 0;

    ret += solve(sum + vec[cnt], cnt + 1);
    ret += solve(sum - vec[cnt], cnt + 1);

    return ret;
}

// int solve(int sum, int cnt) {
//     int ret = 0;
//     if (cnt == n - 1 && sum == vec[n - 1]) {
//         return 1;
//     }
//     else if(cnt == n - 1 && sum != vec[n - 1])
//         return 0;

//     if(sum > 20 || sum < 0) return 0;

//     ret += solve(sum + vec[cnt], cnt + 1);
//     ret += solve(sum - vec[cnt], cnt + 1);

//     return ret;
// }

int main() {
    memset(dp, -1, sizeof(dp));

    cin >> n;

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;

        vec.push_back(a);
    }

    cout << solve(vec[0], 1);
}

 

 

---

 

 

3. Feedback

- DP가 아직은 접근법이 어렵기 때문에 먼저 DP를 생각하지 말고 완전탐색으로 문제를 해결한 후 최적하하는 방식으로 코드를  DP로 변경하는 형태로 연습해야겠다