[JAVA] 백준 1182 - 부분수열의 합

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

1182번: 부분수열의 합

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int[] arr;
    static int n, s;
    static int answer;
    static int[] nums;

    public static void dfs(int start, int cnt, int length, int sum) {
        if (cnt == length) {
            if(sum == s) answer++;
            return;
        }

        for (int i = start; i < n; i++) {
            dfs(i+1,cnt+1, length, sum+arr[i]);
        }

    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());

        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 1; i <= n; i++) {
            dfs(0, 0, i, 0);
        }

        System.out.println(answer);
    }
}

 

브루트포스 문제다. 

부분수열의 길이를 1부터 n까지 돌며

각각의 길이의 부분 수열마다 원소를 다 더한 값이 S가 되는게 있다면 카운팅했다. 

 

그런데 사실 이렇게 dfs for문안에서 호출을 하지 않아도 됐다. 

 

dfs를 호출 할 때 해당 원소를 포함하는 경우, 안 포함하는 경우 이렇게 두가지 경우로 나눠 각각 재귀호출을 해주면 되는 것이였다. 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] arr;
    static int n, s;
    static int answer;

    public static void dfs(int cnt, int sum) {
        if (cnt == n) {
            if(sum == s) answer++;
            return;
        }
        dfs(cnt + 1, sum + arr[cnt]); // 해당 인덱스값 더함
        dfs(cnt + 1, sum); // 해당 인덱스값 안 더함
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());

        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0, 0);

        if(s==0) System.out.println(answer-1); // 공집합의 경우 합이 0이므로 이 경우를 빼줘야 함
        else System.out.println(answer);
    }
}