[BOJ 1182] 부분수열의 합 (C++)

 

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

부분수열의 합 문제

구현 방법

 

이 문제는 백트래킹 알고리즘을 적용해야 하는 문제였습니다.

 

문제의 예제처럼 숫자가 [-7, -3, -2, 5, 8] 이 주어지면, 첫 번째 원소부터 총합으로 더할지 말지 선택하며 차례대로 뻗어나가는 알고리즘입니다.

 

다음 사진은 백준 문제의 예를 알고리즘에 적용한 설명을 하는 사진입니다.

 

 

노드의 값은 탐색하면서 만들어내는 총합을 표시하고, 입력된 수열의 첫번째 원소를 선택해 더하면 오른쪽, 선택하지 않고 넘어가면 왼쪽으로 탐색을 합니다.

 

이렇게 n번까지 탐색하면 모든 경우의 수를 알고, 총합이 s과 같으면 카운트를 늘려줍니다.

 

위 내용을 아래와 같이 구현했습니다.

 

소스코드

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

int n;
int s;
int arr[22];
int cnt;

//func함수는 현재 총합이 sum일때, k번째 원소를 더할지 말지 결정
void func(int k, int sum) {
    if(k == n){
    	//전체 다 탐색했을때 원하는 합이랑 같은경우
        if(sum == s) {
            cnt++;
        }
        return;
    }
    
    //현재 원소를 합에 추가하지 않는 경우
    func(k+1, sum);
    
    //현재 원소를 합에 추가하는 경우
    func(k+1, sum + arr[k]);
}

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

    cin >> n >> s;
    for(int i=0;i<n;i++) {
        cin >> arr[i];
    }
	
    //0번째 원소부터 탐색 시작
    func(0,0);
    
    //원하는 합이 0이면, 수열중 아무것도 선택안해서 총합이 0이 되는 경우 한번 제거
    if(s==0) cnt--;
    
    cout << cnt;
}