[틀림 세모] 백준 5557 1학년 // dfs dp

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

* 풀이

+ , - 2가지 경우의수

완탐 -> 2^100 -> 불가

dp?

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

typedef long long ll;

int n;
int arr[104];
ll dp[104][24]; //(idx, num) : 그떄 경우의수

ll dfs(int idx, int num) {
    if(num <0 || num >20) {
        return 0;
    }
    
    if(idx==n-1) {
        if(num==arr[idx]) {
            // cout<<idx<<" "<<num<<"\n"; 
            return 1;
        }
        return 0;
    }
    
    ll & ret = dp[idx][num];

    if(ret!=-1) {
        return ret;
    }

    ret=0;
    ret+=dfs(idx+1,num+arr[idx]);
    ret+=dfs(idx+1,num-arr[idx]);
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    memset(dp,-1,sizeof(dp));

    cin>>n;
    for(int i=0;i<n;++i) {
        cin>>arr[i];
    }
    
    // cout<<dfs(0,0);
    // 안되는 이유 : 첫숫자를 2번사용하게됨.?

    cout << dfs(1, arr[0]);
    
    return 0;
}

시행착오

마지막 숫자와 같은지 검사, 마지막숫자도 더하거나 빼는것이 아님.

idx는 현재 검사대상임 (검사안함), 종료조건 주의

idx가 n-1일때, num(누적합) 과 arr[idx]를 비교하면 됨.

 

dfs(0,0)으로 시작 하면 안되는이유

반례 ) arr[0]이 0인경우, num 범위체크에서 안걸러짐

정답이 2배가 되는 문제 발생

따라서 , dfs(1, arr[0])으로 호출하거나, dfs(idx+1, num + arr[idx+1])로 구현해야함.

 

max int, max LongLong