알고리즘 풀이 - 백준 1182(부분수열의 합, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

N개의 정수로 이루어진 수열에서 크기가 양수인 부분 수열의 원소를 더한 값이 S가 되는 경우의 수를 구하는 문제

 

 

2. 풀이

 

이 문제는 전형적인 완전 탐색 문제로 N개의 정수로 이루어진 수열 중 1개 이상의 원소를 갖는 모든 부분 집합을 테스트해야 한다.

그리고 그 원소들의 합이 주어진 값 S와 동일한 경우 그 경우의 수를 추가하는 것인데 이 문제는 재귀, 순열, 비트마스크 등의 완전 탐색 기법을 활용하여 해결할 수 있다.

 

그 중, 여기서는 재귀, 비트마스크를 통해 해결해본다. (순열은 관련 문제 포스팅이 일부 있으니 그것을 참조)

 

① 재귀

재귀로 해결하기 위해서는 현재 재귀 함수의 상태, 탈출 조건이 필요하다. 완전 탐색을 하는 경우에는 모든 가능한 경우의 수를 체크해야 하는데 적당한 조건이 주어지지 않으면 잘못된 결과를 낳는다.

이 문제의 탈출 조건은 어떨까?

그것은 현재 마지막까지 모든 부분 집합을 체크했는지이다. 예를 들어 [1, 2, 0]이 전체 집합의 원소인데 찾고자 하는 합은 3이라고 가정하자.

그러면 1부터 시작하여 (1), (2), (0), (1, 2), (1, 0), (2, 0), (1, 2, 0)과 같이 모든 부분 집합을 탐색하게 되는데 재귀를 통해서 탐색 시에는 앞에서부터 시작하여 반복문으로 뒤의 원소까지 탐색하게 되므로 (1, 2)를 탐색한 뒤 (1, 2, 0)을 탐색해야 한다.

그런데 (1, 2)와 (1, 2, 0) 모두 원소의 합이 3이므로 경우의 수에 더해야 하는데 (1, 2)를 탐색 후 탈출해버린다면 모든 경우의 수를 정확히 찾아낼 수 없게 된다.

따라서, 조건에 맞는 경우에는 경우의 수만 추가하고 다음 부분 집합까지 계속 체크를 해야 한다.

 

함수의 현재 상태는 완전 탐색일지라도 이전에 이미 탐색이 완료된 수를 다시 탐색할 필요가 없으므로 이전 탐색된 숫자의 위치를 전달하여 그 이후 부터 탐색하도록 하는 변수와 현재 선택된 숫자의 개수 또한 전달한다.

현재 선택된 숫자의 개수를 전달하는 이유는, 최초에 재귀 함수를 호출 시에 아무 것도 선택되지 않으면 합이 0인데 문제에서 제시된 원소의 합도 0인 경우를 제외하기 위함이다.

 

② 비트마스크

집합의 각 원소를 하나의 비트로 보자. 그러면 부분 집합에 포함된 경우를 1로 놓고, 아닌 경우를 0으로 놓을 수 있다. 즉, 전체 집합을 $2^N$ 꼴로 나타내는 것이 가능해진다.

그러면, N=4라고 가정 시에, 0001 ~ 1111까지 모든 경우의 수를 탐색하도록 반복문을 구성하고 그 때, 현재 비트가 1인 경우들만 체크하여 그 원소를 더한 값이 주어진 값 S와 같은 경우만 체크하면 된다.

전체 집합은 1111인데 이는 (1 << N) - 1로 표현이 가능하다. N번 좌측으로 밀면 현재 범위를 한 번 더 뛰어넘기 때문에 그 경우에서 -1을 해주면 모든 비트를 1로 만든 꼴이 된다.

 

즉, 반복문을 통해 0001=1이므로 1부터 (1 << N) -1 까지 반복하며 값을 체크하는 방식으로 코드를 구현하면 해결할 수 있다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

① 재귀로 해결

import java.io.*;

public class Main{
    static int n;
    static int s;
    static int num[];
    static int ans = 0;
    static int sum = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String line[] = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        s = Integer.parseInt(line[1]);

        num = new int[n];
        line = br.readLine().split(" ");

        for(int i=0; i < n; i++){
            num[i] = Integer.parseInt(line[i]);
        }

        // 재귀함수 시작
        backTrack(0, 0);
        
        bw.write(String.valueOf(ans));
        bw.flush();
        br.close();
    }

    // idx는 부분 수열의 기존 선택된 숫자의 index를 전달하여 그 수부터 이후의 수만 체크
    // 이를 통해 전체 완전 탐색 경우의 수를 줄인다.
    // ch는 현재 몇 개의 숫자가 선택되었는지 확인하는 변수
    private static void backTrack(int idx, int ch){
    
        // 0개 이상의 수가 선택되었고 그 합이 s와 같다면
        if(ch > 0 && sum == s){
            ans++;
        }

        // idx번째 숫자부터 시작하여 나머지 수들을 재귀로 체크한다.
        for(int i=idx; i < n; i++){
            sum += num[i];
            backTrack(i+1, ch+1);
            sum -= num[i];
        }
    }
}

 

② 비트마스크로 해결

import java.io.*;

public class Main{
    static int n;
    static int s;
    static int num[];
    static int ans = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String line[] = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        s = Integer.parseInt(line[1]);

        num = new int[n];
        line = br.readLine().split(" ");

        for(int i=0; i < n; i++){
            num[i] = Integer.parseInt(line[i]);
        }

        // 1부터 시작하여 전체 비트가 1이 되는 모든 경우의 수에 대해 확인
        for(int i=1; i < (1 << n); i++){
            int sum = 0;
            
            // 1을 0~n-1번 비트를 좌측으로 밀어서 현재 포함된 숫자가 무엇인지를 전체 탐색 수행
            for(int j=0; j < n; j++){
                // 만약 0이 아니라면 j번째 수는 현재 포함된 것임
                if((i & (1 << j)) != 0){
                    sum += num[j];
                }
            }
            if(sum == s) ans++;
        }
        
        bw.write(String.valueOf(ans));
        bw.flush();
        br.close();
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.