[Backjoon_1182] 부분수열의 합(Java)

문제링크

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

1182번: 부분수열의 합

문제설명

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

제한사항

제한시간	메모리제한
2초	256MB

문제풀이

위 문제에서 N의 조건은 1보다 크고 20보다 작으므로 최강의 경우를 모두 만든다면 2^20이 된다. 이는 1초 내로 수행할 수 있으므로 모든 방법을 확인하는 재귀를 만들어 구현할 수 있음을 알 수 있다.

이 문제를 조금 다른 방식으로 접근해 보면 N값이 1~20이므로 index라고 생각하고 비트마스크 알고리즘을 사용해서 해결할 수 있다.

 

    public static boolean isEqual(int bit, int[] num, int s){
        int sum = 0;
        for(int idx = 0; bit > 0; idx++){
            if((bit & 1) == 1){
                sum += num[idx];
            }
            bit =  bit >> 1;
        }
        if(sum == s)
            return true;
        else
            return false;
    }

비트 연산을 구현하여준다. bit을 >>연산을 통해 계속 오른쪽으로 옮겨가고 idx위치를 옮겨서 해당 비트가 사용되었는지 체크하고 사용 되었으면 sum에 추가해준다.

그리고 마지막에 결과가 만족하는 수열인지 확인하여  만족하면 true, 아니면  false를 반환받는다.

        int count = 0;
        for(int bit = 1;bit < (int)Math.pow(2,n); bit++) {
            if(isEqual(bit,num,s)){
                count ++;
            }
        }

위에서 구현한 판정 알고리즘을 사용하기 위해  비트 값을 1부터 2^n까지 넣어 값을 만들어 비교를 수행한다. 그러면 모든 bit에 대하여 구현을 하게 되므로 결론적으로 모든 경우의 수를 확인하는 결과가 된다.

구현코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int s = sc.nextInt();
        int[] num = new int[n];
        for(int i = 0; i < n; i++){
            num[i] = sc.nextInt();
        }


        int count = 0;
        for(int bit = 1;bit < (int)Math.pow(2,n); bit++) {
            if(isEqual(bit,num,s)){
                count ++;
            }
        }
        System.out.println(count);
    }

    public static boolean isEqual(int bit, int[] num, int s){
        int sum = 0;
        for(int idx = 0; bit > 0; idx++){
            if((bit & 1) == 1){
                sum += num[idx];
            }
            bit =  bit >> 1;
        }
        if(sum == s)
            return true;
        else
            return false;
    }
}

 

시간복잡도

시간복잡도는 모든 bit에 대하여 돌게 되므로 O(2^n)이 그리고 처리과정에서 n개의 bit를 확인하므로 n을 곱하여

최종적으로 시간복잡도는 O(n*2^n)이 된다.