[java] 백준 부분수열의 합

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

1182번: 부분수열의 합

문제

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

입력

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

출력

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

처음에 입력이 20인 걸 보고 백트래킹을 하면 O(2^n) 이니깐 2 ^ 20 ? 너무 큰데.. 생각했는데

제한 시간을 보니 2초인 것을 보고 백트래킹을 써도 되겠다 판단했다. 

 

DFS 로 풀이했다. 함수의 매개변수(parameter) 는 현재 깊이를 나타내는 depth, 현재까지의 합을 나타내는 sum, 비교할 값인 target 으로 설정했다.  

 

함수를 호출하는 루트를 제외하고 각 함수 호출에서 sum과 target을 비교하면, 전역변수 count ++ 하는 간단한 알고리즘이다. 방문 배열을 사용하는 대신 함수 실행시 각 for문에서 시작값을 이전에 호출한 index +1 값을 주어서 중복 호출을 방지했다. 

 

전체 코드

import java.util.*;
import java.io.*;

class Main{
    static int answer = 0;
    static StringTokenizer st ;
    static int[] arr;
    static int count= 0 ;
    public static void main(String[] argv) throws IOException{
        StringWriter sw  =new StringWriter ();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
  nextLine(br.readLine());
  
   int n = Integer.parseInt( st.nextToken());
   int s = Integer.parseInt( st.nextToken());
    arr = new int[n];
    
   nextLine(br.readLine());
   
   for(int i =0  ;i< n; i++) {
	arr[i] = nextInt();
   }
	   dfs(0, 0, s);
   
   System.out.println(count);

    }
    public static void dfs(int depth, int sum,int target) {
    	if(depth > 0 && sum == target ) count++;
    	if(depth >= arr.length) {
    	return;	
    	}
    	for(int i = depth; i< arr.length; i++) {
    		dfs(i+1, sum+arr[i] , target);
    	}
    }
    public static void pl() {
    for(int i =0 ;i < arr.length ;i++)
    {
    System.out.print(arr[i] + " ");
    }System.out.println();
    }
    public static void nextLine(String br) {
    		st = new StringTokenizer(br);
    }
    public static int nextInt() {
    	if(st == null)throw new NullPointerException("st가 비어있음");
    	return Integer.parseInt(st.nextToken());
    }
  
}