[알고리즘] 백준 > #1182. 부분수열의 합

오늘은 부분수열의 합이라는 문제를 풀었다.

문제링크

#1182. 부분수열의 합

풀이방법

해시태그를 보면 알 수 있듯이, 완전탐색을 이용해 풀었다.
이유는 N의 범위에 있는데, 1 <= N <= 20이기 때문에 2^20, 대략 백만번이기 때문에 완탐으로도 충분!! (대애충 컴퓨터가 1초에 가장 간단한 연산을 1억번한다고 생각했습니다)

완탐(dfs)으로 각 원소가 부분수열에 속하냐(visited == true) 속하지 않냐(visited == false)를 따지고 속하면 sum하는 방식이다.

코드

import java.util.Scanner;

public class SumOfSubarray {
    static int n;
    static int s;
    static int[] numbers;

    static boolean[] visited;

    static int result = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        s = scanner.nextInt();

        numbers = new int[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = scanner.nextInt();
        }

        visited = new boolean[n];

        dfs(0);

        System.out.print(result);
    }

    private static void dfs(int start) {
        if (checkSum()) result++;

        for (int i = start; i < n; i++) {
            visited[i] = true;
            dfs(i + 1);
            visited[i] = false;
        }
    }

    private static boolean checkSum() {
        int sum = 0;
        boolean flag = false;

        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                sum += numbers[i];
                flag = true;
            }
        }

        if (flag && (sum == s)) return true;
        else return false;
    }
}

그냥 visited를 사용한 dfs로 풀었는데 추후에 공부겸 bit를 사용해서도 풀어볼 예정!!