(C++) 백준 1182번 부분수열의 합. dfs와 백트래킹

1. 필요한 개념

- dfs 란(뇌피셜 정리.. )

 : 재귀를 통해 전체 경우를 다 보는 탐색을 말한다

  > 이때 전체 경우를 다보는 경우도 있고, 경우를 찾으면 멈추는 경우도 있음! 

 

- 백트래킹

백트래킹이란 dfs에서 뒤에서부터 모든 순열을 다 조합하는 것이다.

(주로 내가 이럴 때 쓰는데 정의가 이것은 아니다..)

 

 

 

2. 문제 

 

 

3. 풀이

 

부분 수열이란 한 수열에서 특정 숫자를 골라서 만든 수열이다.

즉 특정 숫자가 들어가고/안 들어가고 두 가지의 경우로 나뉜다. 

(고등학교 때 부분수열의 개수가 공집합 포함해서 2^N개인 거 배웠죠,, 그런 개념)

 

그래서 나는 dfs(int 인덱스, int 합)인 함수를 만들고

 - 해당 인덱스의 숫자가 들어가는 경우 : sum = sum + arr [i] // arr은 원래 수열! 

 - 해당 인덱스 숫자가 안들어가는 경우 : sum = sum

 

두 가지로 나누어서 dfs를 두번 호출하였다. 

그리고 당연하지만 sum + arr[i] 가 target 하는 숫자이면 answer++;을 통해 답 개수를 하나 늘렸다.  

 

 여기서 두가지의 헷갈림 포인트가 있었는데 하나씩 짚어보겠다. 

   1.  sum == target -> answer ++;을  해줘도 되지 않냐

이러면 sum == target일때랑 sum+arr[i] == target일때랑 겹친다. 할거면 둘중에 하나만 해야 된다.. 

 

근데 마지막 숫자가 부분수열에 들어갈 경우, 인덱스가 6(7번째 값이 들어오면)이면 바로 리턴을 해줘버리기 때문에 

sum = sum + arr[5]일때 요소가 넘겨지면 넘어온 sum == answer로 캐치하지 못하고 리턴해버린다. 

이걸 수정한다면 sum == target일때 answer ++; 해줘도 상관없을 듯 하다..  

 

   2.  sum+arr[i] == target 이면 리턴을 해줘야 되지 않냐

예를 들어 타겟숫자가 0이고 순열이 -1 1 -2 2이 있다면

부분순열 -1 1 / -2 2 는 잡히지만 -1 1을 잡고나면 리턴하므로 아무리 해도 -1 1 -2 2 부분수열이 잡히지 않는다.

 

문제에서 물어본 것은 "합이 target인 부분수열의 개수"이므로 리턴을 중간에서 해주면 안되고

무조건 인덱스 끝번호까지 들어갈지 말지 결정한 다음에 리턴해야 된다!!

 

 

 

4. 코드

 

#include <iostream>
using namespace std;

int n, target, sum, answer;
int arr[20];


//모든 경우의수 : 모든 숫자가 들어가거나 안들어가거나
// 따라서 2의 n승 

// -----dfs도 두가지 경우로 나눈다 ---- 
// 1. 해당 숫자가 들어갈때 : sum += 현재숫자
// 2. 해당 숫자가 안들어갈때 : sum = sum

void dfs(int i, int sum) {

    //모든 수를 다 더하면 리턴
    if (i == n) return;

    //지금까지의 합에서 현재를 더함 > 정답이면 카운트 1
    if (sum + arr[i] == target) answer++;

    //아니면 dfs를 계속 돌린다
    //현재 숫자를 안더하고 (넘어가고) 다음 숫자를 받는 경우
    dfs(i + 1, sum);

    //sum = sum + 현재값
    dfs(i + 1, sum + arr[i]);
}

int main() {

    cin >> n >> target;
    
    for (int i = 0; i < n; i++)cin >> arr[i];

    answer = 0;
    dfs(0, 0);

    cout << answer;

    return 0;
}

 

 

p.s. 5달 전에 풀었던 문제였다. 어쩐지 술술 풀리더라ㅋㅋㅋ