[백준 자바 1182] 부분수열의 합 (실버 2)

 

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

1182번: 부분수열의 합

 

 

처음에는 조합으로 풀면 되겠다 싶어서 풀었다. 

계속 안 풀렸는데, 공집합인 경우도 있어서 depth 가 0보다 큰 경우에 카운팅 하도록 했다. 

 

그리고 제출 후, 구글링을 해보니 다 나랑 다른 풀이로 풀었었다. 

가장 이해가 되는 사진이 있어서 가져와보면, 

출처 : https://velog.io/@ilil1/%EB%B0%B1%EC%A4%80-1182%EB%B2%88-java

 

재귀인 것은 똑같지만, 현재 값을 포함하는 경우와 포함하지 않는 경우로 트리 구조로 가져가서 풀었다. 

 

두 풀이의 드라마틱한 성능 차이는 없었다. 

 

 

 

 

---

전체 코드1 

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

public class Main {

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    static int N, S, ans;
    static int[] nums;

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

        N = stoi(st.nextToken());
        S = stoi(st.nextToken());

        nums = new int[N];

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            nums[i] = stoi(st.nextToken());
        }

        Arrays.sort(nums);

        bt(0, 0, 0);

        System.out.println(ans);
    }

    static void bt(int depth, int start, int total) {
        if (total == S && depth > 0) { // 합이 S가 되는 부분순열.
            ans++;
        }
        if (depth == N) { // 끝까지 배열을 돌아도 S보다 작음
            return;
        }

        for (int i = start; i < N; i++) { // 순서가 없는 조합
            bt(depth + 1, i + 1, total + nums[i]);
        }
    }
}

전체 코드2 

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

public class Main {

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    static int N, S, ans;
    static int[] nums;

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

        N = stoi(st.nextToken());
        S = stoi(st.nextToken());

        nums = new int[N];

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            nums[i] = stoi(st.nextToken());
        }

        bt(0, 0);

        System.out.println(S == 0 ? ans - 1 : ans);
    }

    static void bt(int depth, int total) {
        if (depth == N) {
            if (total == S) {
                ans++;
            }
            return;
        }

        bt(depth + 1, total);
        bt(depth + 1, total + nums[depth]);
    }
}

 

 

첫 번째 제출은 코드2, 두 번째 제출은 코드1 이다. 

메모리나 시간이나 큰 차이가 없다.

 

---

 

참고 링크

• https://velog.io/@ilil1/%EB%B0%B1%EC%A4%80-1182%EB%B2%88-java