백준 5557번 1학년 - C++(cpp) 풀이

---

 

1. dp(val, idx)를 현재까지의 계산값이 val이고 idx번째 수~마지막 수까지 고려할 때 만들 수 있는 등식의 수라고 하자.
2. dp(val, idx) = dp(val+arr[idx], idx+1) + dp(val-arr[idx], idx+1) 이다.
3. 최종적으로 구해야하는 값은 dp(arr[0], 1)이다.

 

1. dp(val, idx)를 현재까지의 계산값이 val이고 idx번째 수~마지막 수까지 고려할 때 만들 수 있는 등식의 수라고 하자.

 백트래킹으로 풀이하게되면, 최대 2^98번을 탐색하므로 시간초과가 발생한다. 중간 계산값이 0 이상 20 이하로 제한되어 있으므로 DP를 이용해서 풀이할 수 있다. dp(val, idx)를 현재까지의 계산값이 val이고 idx번째 수부터 고려할 때 만들 수 있는 올바른 등식의 수라고 하자.

 

2. dp(val, idx) = dp(val+arr[idx], idx+1) + dp(val-arr[idx], idx+1) 이다.

 각 숫자 사이에는 덧셈기호, 혹은 뺄셈기호 두 가지중 하나를 넣을 수 있으므로, dp(val, idx) = dp(val+arr[idx], idx+1) + dp(val-arr[idx], idx+1)이 된다. 기저 사례는 idx = N-1일 때로, 마지막에는 등호를 넣어야 하므로 현재까지의 계산값인 val과 마지막 수인 arr[N-1]이 일치하는지 확인하여 일치한다면 1, 아니라면 0을 리턴해준다.

 

3. 최종적으로 구해야하는 값은 dp(arr[0], 1)이다.

 첫 번째 연산 기호가 들어가야 하는 곳은 arr[0]과 arr[1] 사이이다. 따라서 최종적으로 구해야 하는 값은 dp(arr[0], 1)이 된다.

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

typedef long long ll;

int N;
ll arr[101], cache[21][101];

// dp(val, idx): 현재까지의 계산값이 val이고 idx번째 수~마지막 수까지 고려할 때 만들 수 있는 등식의 수
ll dp(ll val, int idx) {
    if (idx == N-1) {
        if (val == arr[idx]) return 1;
        else return 0;
    }
    
    ll& ret = cache[val][idx];
    if (ret != -1) return ret;
    
    ret = 0;
    if (val+arr[idx] <= 20) ret += dp(val+arr[idx], idx+1);
    if (val-arr[idx] >= 0) ret += dp(val-arr[idx], idx+1);
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    memset(cache, -1, sizeof(cache));
    
    cin >> N;
    for (int i=0; i<N; i++) cin >> arr[i];
    
    cout << dp(arr[0], 1);

    return 0;
}