백준 1182 부분수열의 합 (JAVA)

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

1182번: 부분수열의 합

 

처음엔 index와 depth를 dfs 매개변수로 잡고,

depth가 index만큼 dfs 실행하여 추출한 배열 요소들을 더한 뒤,

S와 비교하는 방식으로 구현해봤는데 아쉽게도 시간초과라 다른 방법을 생각하느라 시간을 많이 할애한 문제입니다.

결국엔 구글링의 도움을 받긴 했지만, 한가지 얻어갈 수 있었던건 dfs를 구현할 때 꼭 반복문이 들어가야 한다고 생각한 저의 고정관념을 고칠 수 있었던 것이었습니다.

 

 

import java.util.Scanner;
 
public class Main {
    static int arr[];
    static int N, S, res = 0, MAX = 20;
 
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        S = sc.nextInt();
        arr = new int[MAX];
 
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        sc.close();
 
        dfs(0, 0);
 
        System.out.println(res);
    }
 
    public static void dfs(int idx, int sum) {
        if (idx == N)
            return;
        if (sum + arr[idx] == S)
            res++;
 
        dfs(idx + 1, sum);
        dfs(idx + 1, sum + arr[idx]);
 
    }
}