백준 1182 C++

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

1182번: 부분수열의 합

 

 

나 난독 있나봐...

 

 

생각

숫자가 들어가는 경우 / 안들어가는 경우로 나눠 dfs를 돌리자
1. sum += arr[1];
2. sum = sum;

 

 

코드 초안 약간 이런 느낌

void dfs(int k, int sum){
    for(int i=0 ; i<N ; i++){
        if(){ //숫자가 들어가는 경우에 대한 조건?    
        sum += arr[i];
        dfs(k+1, sum);
        }

        else{
            sum = sum;
            dfs(k+1, sum);
        }

        if (sum == S){
            cnt++;
        }
    }
}

 

다음 코드의 문제점

1. 공집합 생각 안함

 -> main에서 S가 0일때만 공집합을 하나 빼주자~

2. if 처리를 어떻게 해야할지 모르겠음!!!

 -> 그냥 for문을 안돌리고 dfs 계속 재귀로 호출하면 될 듯!!

     그리고 sum 저장하고 매개변수로 sum 넣는 것 보다 한 번에 쓰는 게 더 보기 좋을 것 같다!

     dfs(k + 1, sum + arr[k]); 이런 식으로!

 

정답 코드

#include <iostream>
using namespace std;

int N, S, cnt;
int arr[21];

void dfs(int k, int sum) {
    if (k == N) {
        if (sum == S) {
            cnt++;
        }
        return;
    }
    dfs(k + 1, sum + arr[k]);
    dfs(k + 1, sum);
}

int main() {
    cin >> N >> S;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    dfs(0, 0);
    if (S == 0) {  // S == 0인 경우 공집합도 포함되니까 하나 감소
        cnt--;
    }
    cout << cnt;
    return 0;
}