[BOJ] 백준 1182 부분수열의 합 / 완전 탐색(Brute-force Search)

이미지를 클릭하면 문제 사이트로 이동합니다.

---

💣 문제 이해

N개 (20개 이하) 의 정수로 이루어진 수열이 입력으로 주어지고

그 수열 내에서 원소 개수가 양수인 부분수열 중 합이 S 인 수열의 개수를 구하라는 문제이다.

 

문제를 풀면서 DFS, 백트래킹이 생각났고, 실제 다른 블로거 분들도 그렇게 풀이를 하는 경우도 있었다.

DFS와 백트래킹 문제풀이를 할 때, 그 방식으로도 풀어보기로 하고,

 

이번에도 또한 완전 탐색(Brute-force Search) 방식을 사용하기로 했다. (이름은 그렇고 암튼 재귀호출함..)

 

 

💭 풀이 과정

 

작성 언어: C++

 

#include <cstdio>

int num[25] = {0,};
int inpCnt = 0, inpSum = 0, answer = 0;

void count(int pIndex, int pSum){
    pSum += num[pIndex];
    // 넘겨받은 인덱스가 입력받은 숫자의 개수를 넘은 경우 종료.
    if (pIndex >= inpCnt)   return;
    if (pSum == inpSum) answer++;
    
    count(pIndex + 1, pSum - num[pIndex]);  // 자기 자신을 제외한 합을 넘겨줌
    count(pIndex + 1, pSum);    // 자기 자신을 포함한 합을 넘겨줌
}

int main(){
    scanf("%d %d", &inpCnt, &inpSum);
    for (int i = 0; i < inpCnt; ++i) {
        scanf("%d", &num[i]);
    }
    // 맨 처음은 배열의 첫번째 원소부터 더하기 시작하고, 아직 합은 0이다.
    count(0, 0);

    printf("%d\n", answer);
    return 0;
}

 

 

🏆 배운 점

 

최악의 경우라 하더라도 2²⁰ 정도라서(약 1,000,000) 가능한 재귀호출 방법이었다.

 

이후에 DFS, 백트래킹을 다룰 때 다시 풀어보면서 비교하면 좋은 공부가 될 것 같다.