[BOJ] 1182번 부분수열의 합

문제

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

1182번: 부분수열의 합

 

 

풀이

지금 껏 해왔던 방법대로 조합을 구하기 위해서 tmp라는 임시 정수 배열을 이용해서 구했다. 항상 이 방법을 사용하면서 추가적인 공간을 사용하기 때문에 더 좋은 방법은 없나 알아봤었지만 재귀에 익숙하지 않았기 때문에 다른 사람의 코드를 봐도 이해가 잘 되지 않았다. 이에 반성하고 공간 복잡도를 줄일 수 있도록 더 공부해서 개선된 코드를 추후에 추가해야겠다.

우선 내가 알던 방식으로 푼 방식의 코드이다.

 

import java.util.*;
public class Main {
    static Scanner scan = new Scanner(System.in);
    static int answer=0;
    static int N,n_sum, cnt;
    static int[] arr, tmp;
    static void init() {
        N = scan.nextInt();
        n_sum = scan.nextInt();
        arr = new int[N];
        tmp = new int[N];
        for(int i=0;i<N;i++)
            arr[i] = scan.nextInt();
    }
    static void all_case_set(int st, int depth, int std) {
        if(depth==std) {
            int t_sum=0;
            for(int i=0;i<std;i++)
                t_sum+=tmp[i];
            if(t_sum==n_sum)
                cnt++;
            return;
        }
        for(int i=st;i<N;i++) {
            tmp[depth] = arr[i];
            all_case_set(i+1,depth+1,std);
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        init();
        for(int i=1;i<=N;i++)
            all_case_set(0,0,i);
        System.out.println(cnt);
    }
}