백준 1182번 - 부분수열의 합

백트래킹

(1) 경우에 해당하는 문제인 백준 1182번을 보도록 하자
기존에는 1개,2개, ... N 개 뽑을 때의 모든 조합에 대해서 sum 을 구하고 해당 sum 이 S 가 될 때마다 경우의 수를 증가시키려고 했다

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

public class Main {
    static int N, S;
    static int[] number;
    static int count = 0;

    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());

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

        // 조합 구해서 1,2, ... N 개 뽑을 때까지 반복
        for (int i = 1; i <= N; i++) {
            getCombination(0, i, 0, 0);
        }
        System.out.println(count);
    }

    public static void getCombination(int depth, int target,int prevOrder, int sum) {
        if (depth == target && sum == S) {
            count++;
            return;
        }

        for (int i = 0; i < N; i++) {
            if (prevOrder <= i) {
                getCombination(depth + 1, target, i + 1, sum + number[i]);
            }
        }
    }
}

하지만 백준에서 풀이시간을 확인한 결과 736ms 로 상당히 오래 걸리는 풀이임을 알게 되었고 그 이유가 combination 에서 비교하는 if 문이 존재하기 때문임을 알게 되었다. for 문안에 1줄이 추가될 때마다 매번의 depth 마다 depth*N 번의 비교가 일어나게 된다

새로운 풀이

package Baekjoon;

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

public class Main {
    static int N, S;
    static int[] number;
    static int count = 0;

    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());

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

        getCombination(0, 0);
        if(S==0) count--;
        System.out.println(count);
    }

    public static void getCombination(int depth, int sum) {
        if (depth == N) {
            if (sum == S) {
                count++;
            }
            return;
        }

        getCombination(depth + 1, sum);
        getCombination(depth + 1, sum + number[depth]);
    }
}