BOJ 1182 - 부분수열의 합

 

1182번: 부분수열의 합

 

1. 아이디어

먼저 정답의 최대치 계산해보기

먼저 N의 최대치가 20이이니까 부분수열의 개수는 최대 2^20 -> int N 결정

부분수열의 합은 최대 20*1,000,000 -> int S 결정

 

 

N개의 정수를 중복을 허용하지 않고 합이 S가 되는 진부분수열을 구하는 문제

 

1~N 크기의 부분수열 전부 체크해서 합이 S가 되는 경우 찾으면 되겠다!!!

부분 수열은 중복을 허용하지 않고 순서도 고려하지 않기 때문에 조합으로 구하면 될 거 같다.

 

2. 시간복잡도

조합의 시간 복잡도는 O(2^N)이고 N번 도는 for문 안에 있으니까 총 O(N*2^N)

 

N의 최댓값이 20이므로 20*2^20 < 2초 라서 가능한 풀이법이다.

 

3. 구현

 

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, S, ans;
    static int[] nums, selected;

    public static void main(String[] args) throws IOException {
        init();

        for (int i = 1; i <= N; i++) {
            rec_func(1, 0, i);
        }

        bw.write(ans + " ");

        bw.close();
    }

    private static void rec_func(int k, int prev, int M) throws IOException {
        if (k == M + 1) {
            int sum = 0;
            for (int i = 1; i <= M; i++) {
                sum += selected[i];
            }

            if (sum == S) {
                ans++;
            }
        } else {
            for (int i = prev + 1; i <= N; i++) {
                int n = nums[i];

                selected[k] = n;

                rec_func(k + 1, i, M);

                selected[k] = 0;
            }
        }
    }

    static void init() 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());
        ans = 0;

        selected = new int[N + 1];
        nums = new int[N + 1];

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

 

 

 

다른 풀이

포함시킬 지(1) 말지(0)로 중복을 허용하여 순서있게 0과 1을 나열하는 방법

 

이 경우에는 S가 0일 때 아무것도 안해도 ans가 1 증가하니까 예외로 1 빼줘야 한다

 

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, S, ans;
    static int[] nums, selected;

    public static void main(String[] args) throws IOException {
        init();

        rec_func(1);

        if (S == 0) {
            ans--;
        }

        bw.write(ans + " ");

        bw.close();
    }

    private static void rec_func(int k) {
        if (k == N + 1) {
            int sum = 0;

            for (int i = 1; i <= N; i++) {
                if (selected[i] == 1) {
                    sum += nums[i];
                }
            }

            if (sum == S) {
                ans++;
            }
        } else {
            for (int i = 0; i <= 1; i++) {
                int n = nums[i];

                selected[k] = i;

                rec_func(k + 1);

                selected[k] = 0;
            }
        }
    }

    static void init() 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());
        ans = 0;

        selected = new int[N + 1];
        nums = new int[N + 1];

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