백준 1182번 부분수열의 합 (java)

[Silver II] 부분수열의 합 - 1182

문제 링크

성능 요약

메모리: 14228 KB, 시간: 136 ms

분류

백트래킹, 브루트포스 알고리즘

제출 일자

2024년 3월 30일 17:40:34

문제 설명

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

입력

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

출력

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

 

풀이

부분수열을 모두 찾고 부분수열의 합과 S값이 같은지 확인하면 되는 문제다. 

나는 부분수열을 찾는 방법으로 저번 문제와 똑같이 dfs를 사용했다.

부분 수열을 찾는 것이므로 다음 재귀함수의 반복문은 처음부터 다시 시작할 필요가 없으므로 현재 반복문의 어디까지 돌았는지를 인자에 같이 넣어줬다.

 

package hello.core.backjoon;
import java.io.*;
import java.util.*;
import java.math.*;
import java.lang.*;

public class Main{
    static int x[], N, S=0,cnt=0;
    static Boolean selec[];
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        x = new int[N];
        selec = new Boolean[N];
        st = new StringTokenizer(bf.readLine());

        for(int i = 0 ;i<N;i++){
            x[i] = Integer.parseInt(st.nextToken());
            selec[i] = true;
        }

        dfs(0,0);

        bw.write(String.valueOf(cnt));
        bw.flush();

    }

    public static void dfs(int exsum,int flag){
        if(exsum == S && flag > 0){
            cnt++;
        }
        for(int i = flag ;i<N;i++){
            dfs(exsum + x[i],i+1);
        }
    }
}