[백준 1182] 부분수열의 합

[jusung-c]

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

---

아이디어

N개의 정수를 중복을 허용하지 않고 합이 S가 되는 크기가 양수인 부분수열을 구하는 문제다.

1~N 크기의 부분수열을 전부 완전탐색으로 구해서 합이 S가 되는 경우를 찾으면 되겠다!!!

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

---

시간 복잡도

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

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

---

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

public class Main {
    static int N, S, ans;
    static int[] nums, visit, selected;

    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        // 크기가 양수인 부분수열이니까 1~N 크기의 부분수열 전부 체크
        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];
            }

            // S랑 같으면 ans++
            if (sum == S) {
                ans++;
            }

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

                selected[k] = n;
                visit[i] = 1;

                rec_func(k+1, i, M);

                selected[k] = 0;
                visit[i] = 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());

        visit = new int[N + 1];
        selected = new int[N + 1];
        ans = 0;

        nums = new int[N + 1];

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

    }
}

---

[ghdcksgml1]

<sup>지수</sup>

이 태그를 쓰면 시간복잡도 표현 가능합니당.

N²

[jusung-c]

😲