[C++] SWEA 2817 - 부분 수열의 합

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7IzvG6EksDFAXB&categoryId=AV7IzvG6EksDFAXB&categoryType=CODE

SW Expert Academy

<풀이>

1. 주어진 수열의 각 원소를 모든 경우에 따라 더해본다.

2. 원소들의 합이 K인 경우의 수를 출력한다.

 

<해법>

가장 기본적인 브루트 포스 문제라고 생각합니다. 원소를 고를 때 중복을 제거하는 방식을 고려하여 구현하였습니다.

 

#include <iostream>
 
using namespace std;
 
int N, K;
int arr[20];
int answer;
 
void makeSum(int idx, int sum) {
 
    //합이 K를 넘는 경우 -> 더 이상 더할 필요없으므로 종료
    if (sum > K) {
        return;
    }
 
    //합이 K인 경우 -> answer갱신 후 종료
    if (sum == K) {
        answer++;
        return;
    }
 
    //자신보다 뒤에 있는 원소 더해보기(중복 제거 위해)
    for (int i = idx; i < N; i++) {
        makeSum(i + 1, sum + arr[i]);
    }
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0, K = 0;
        answer = 0;
 
        //입력
        cin >> N >> K;
        for (int i = 0; i < N; i++) {
            cin >> arr[i];
        }
 
        //해법
        /*
        모든 원소 다 더해보기
        */
        makeSum(0, 0);
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

브루트포스에 대해 알아볼 수 있는 문제였습니다.