[백준 - 1182] 부분수열의 합 - Java

문제 설명

 

1182번: 부분수열의 합

 

풀이 : Success

소스 코드

본 풀이는 유셩장님의 기술블로그를 참고한 내용입니다.

import java.util.Scanner;

class Main {

    static int n, s, result = 0;
    static int[] arr;

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        s = sc.nextInt();
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        dfs(0, 0);

        System.out.println(result);
    }

    public static void dfs(int index, int sum) {
        if (index == n) return;
        if (sum + arr[index] == s) result++;

        dfs(index + 1, sum);
        dfs(index + 1, sum + arr[index]);
    }
}

 

풀이 회고

이 문제에서 요구하는 것은 주어진 수열에서 원소가 최소 1개 이상인 모든 부분수열 중에서 원소 값들의 합이 입력된 s값과 일치하는 부분수열의 개수(경우의 수)이다. 해당 문제는 깊이 우선 탐색(depth first search)을 이용하여 해결할 수 있었다.

 

dfs 메서드를 별도로 선언한 후 다음과 같이 2개의 재귀함수를 이용했는데, 이를 통해 주어진 수열에서 원소가 최소 1개 이상인 모든 부분수열의 경우의 수를 탐색할 수 있게 된다.

dfs(index + 1, sum);
dfs(index + 1, sum + arr[index]);

 

index = 0, sum = 0인 재귀함수(dfs(0,0))가 실행된 이후 모습을 보면 다음과 같이 부분수열의 합(sum)이 확장되는 것을 확인할 수 있다. 여기서 arr은 주어진 수열 각각의 원소를 순서대로 저장하고있는 배열이다. (arr[0] : 첫번째 원소, arr[1] : 두번째 원소, ...)

 

 

위 그림에서 dfs(index + 1, sum)만 호출되게 된다면 가장 위에 있는 분기(원소 한 개로 이루어진 부분수열)로 향하는 것으로 생각할 수 있고, dfs(index + 1, sum + arr[index])만 호출되게 된다면 가장 아래에 있는 분기(주어진 수열과 동일한 부분수열)로 향하는 것으로 생각할 수 있다.

 

이때 dfs 함수 내에서 index가 주어진 수열의 원소 개수(n)와 같다면 종료시켜주어야 하는데, 이는 배열 arr의 크기는 n이나 최대 인덱스는 n-1이기 때문이다.(재귀 함수의 종료 조건 설정) 마지막으로 각각의 경우에서 부분수열의 합이 s와 일치하면 결과값을 1씩 증가시켜주도록 선언하면 dfs(0, 0) 호출만으로 원하는 값을 구할 수 있다.

 

 

참고자료

• https://www.acmicpc.net/problem/1182
• https://sihyungyou.github.io/baekjoon-1182/