[BOJ/백준] 부분수열의 합 (dfs)

백준 1182: 부분수열의 합
- 풀이
- 정답 코드 (DFS)
마무리

3년동안 잊었던 알고리즘 능력을 상승시키기 위해 문제를 풀고 있습니다. 한 번 걸었던 길은 빠르게 갈 수 있다고 생각합니다. 이번에 소개해드릴 문제는 dfs를 이용하여 부분수열의 합의 경우의 수를 구하는 문제를 소개해드리도록 하겠습니다.

백준 1182: 부분수열의 합

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

문제의 내용이 위와 같은데, 크기가 양수인 부분수열이라고 해서 약간 헷갈렸지만 크기는 부분수열의 길이라고 생각하시면 될 것 같습니다.

풀이

이 문제는 경우의 수를 모두 구하는 문제이므로 전체 탐색을 쉽게 떠올릴 수 있고, dfs를 이용하여 문제를 풀 수 있습니다.

정답 코드 (DFS)

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

public class Boj1182 {
    private static int n; // 수열의 길이
    private static int s; // 합계

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] ins;
        ins = br.readLine().split(" ");
        n = Integer.parseInt(ins[0]);
        s = Integer.parseInt(ins[1]);

        int[] numbers = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        // 수열의 각 자리의 사용 여부를 체크 하기 위한 배열
        boolean[] used = new boolean[n];

        int count = dfs(0, numbers, used);
        bw.write(count + "");
        bw.flush();
        bw.close();
    }

    public static int dfs(int idx, int[] numbers, boolean[] used) {
        // 마지막 자리에 도달하면 합계를 계산한다.
        if (idx == n) {
            int sum = 0;
            int usedCount = 0;

            for (int i = 0; i < n; i++) {
                if (used[i]) {
                    sum += numbers[i];
                    usedCount += 1;
                }
            }

            // 한개도 사용되지 않은 경우는 무조건 카운팅하지 않는다.
            if (usedCount == 0) {
                return 0;
            }

            return sum == s ? 1 : 0;
        }

        // 새로운 배열을 생성한다.
        boolean[] curNotUsed = new boolean[n];
        boolean[] curUsed = new boolean[n];

        // 사용된 배열을 각각 복사한다.
        System.arraycopy(used, 0, curNotUsed, 0, n);
        System.arraycopy(used, 0, curUsed, 0, n);

        int count = 0;

        // 현재 위치를 사용하지 않고 다음 자리로 이동
        count += dfs(idx + 1, numbers, curNotUsed);

        // 현재 위치를 사용하고 다음 자리로 이동
        curUsed[idx] = true;
        count += dfs(idx + 1, numbers, curUsed);

        return count;
    }
}

마무리

DFS의 경우, 가장 기본이 되면서 다른 알고리즘과 섞여서 자주나오는 알고리즘 중에 하나입니다. 따라서 필수적으로 익히셔야 하는 알고리즘입니다. 혹시 궁금하신 점이나 이상한 점이 있다면 댓글 부탁드리겠습니다.

감사합니다.

#능력 회복하기,
#백준,
#백준 1182,
#부분수열의 합,
#알고리즘

글이 도움이 되셨다면, 커피 한 잔만 사주세요!

Comments

Copied to clipboard

[BOJ/백준] 부분수열의 합 (dfs)

Table of Contents

백준 1182: 부분수열의 합

풀이

정답 코드 (DFS)

마무리