02.08. 부분수열의 합[Brute-force Search][백준 1182]

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

1182번: 부분수열의 합

 

Algorithm classification : Brute-force Search, Back tracking

 

02.08.1. Problem

Write a program to find the number of cases in which the sum of all the elements of a subsequence among positive subsequences is S when there is a sequence of N integers.

 

02.08.2. Input limit

The first line is given an integer N and an integer S indicating the number of integers. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) In the second line, N integers are given with spaces in between. The absolute value of the given integer does not exceed 100,000.

 

02.08.3. Output

In the first line, print the number of subsequences whose sum is S.

 

02.08.4. Solution

시간 제한이 무려 2초군요. 아주 널널한 편입니다. 경우의 수를 다 생각해보면 2^20이니까 DFS나 재귀로 짜는 것이 효율적이 겠네요. 이를 통해 각 원소를 포함시킬지 말지 효율적으로 프로그래밍 할 수 있습니다.

void cal(int idx, int sum)
{

        sum += arr[idx]; //우선 해당 숫자를 더한다
        //범위에 도달할 경우
        if (idx == n)
            return;
        //조건 성립시
        if (sum == s)
            result++;
        //해당 숫자를 안 더했을 경우
        cal(idx + 1, sum - arr[idx]);
        //해당 숫자를 더헀을 경우
        cal(idx + 1, sum);
}

각 원소를 포함시킬지 말지만 어떻게 짤지 고민하면 이 문제는 다 해결한 것입니다. 요런 아이디어는 중요하니 킵해두는 것을 추천드립니다. 처음 접하시는 분들은 생각하기 어려우실 수도 있어요. 보통 for문으로 먼저 접근하시는데, 어떻게 해야할지 고민되거든요. 기저사례만 확실하다면 for문보다 재귀호출이 더 좋아보입니다.