[백준/C++] 1182번 부분수열의 합

 

풀이

백트래킹 문제이다.

1. 먼저 입력값으로 주어지는 배열의 크기 N과 부분수열의 합 S를 입력는다.
2. 배열 arr[20]에 N개의 원소를 입력받는다.
3. 재귀 함수 dfs를 구현합니다. 이 함수는 현재 인덱스(idx)와 현재까지의 합(sum)을 인자로 받는다.
4. 재귀 함수 dfs의 동작은 다음과 같다:
   • 현재 인덱스의 원소를 합에 더해줍니다: sum += arr[idx];
   • 만약 합이 S와 같다면, 카운트를 증가시킵니다: if (sum == S) { cnt++; }
   • 현재 인덱스의 다음 원소부터 탐색하기 위해 for문을 사용하여 재귀 호출합니다: for (int i = idx + 1; i < N; i++) { dfs(i, sum); }
5. 모든 원소에 대해 dfs를 호출하여 부분수열의 합이 S와 같은 경우의 수를 구한다.
6. 최종적으로 cnt를 출력한다.

 

코드

#include <iostream>
using namespace std;

int N, S;
int arr[20];
int cnt = 0;

void dfs(int idx, int sum) {
    sum += arr[idx];  // 현재 인덱스의 원소를 더해줍니다.

    // 부분수열의 합이 S와 같다면 카운트를 증가시킵니다.
    if (sum == S) {
        cnt++;
    }

    // 현재 인덱스의 다음 원소부터 탐색합니다.
    for (int i = idx + 1; i < N; i++) {
        dfs(i, sum);  // 재귀 호출로 다음 원소를 포함시킵니다.
    }
}

int main() {
    cin >> N >> S;

    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    // 각 원소를 시작점으로 하여 dfs를 수행합니다.
    for (int i = 0; i < N; i++) {
        dfs(i, 0);
    }

    cout << cnt << endl;

    return 0;
}

 

 

 

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

1182번: 부분수열의 합