[Java] 백준(실버-2) 1182번 - 부분수열의 합

문제 풀이

---

이 문제는 재귀를 통한 백트래킹 유형으로 풀 수 있는 문제 중 하나이다.

아이디어 도출

이 문제에서는 수열에 담긴 배열의 원소를 선택하는 경우와 선택하지 않는 경우를 구분하는 것이 핵심이다.

생각해낸 아이디어를 먼저 살펴보자.

1. dfs로 배열을 탐색하며, 배열의 모든 원소로 포함시켜 만드는 부분수열과, 포함시키지 않는 부분수열을 만들어간다.
2. dfs의 깊이가 N(수열의 길이의 끝)이 된다면, 부분 수열의 합이 S가 되는지 확인하고 경우의 수를 1 증가시킨 후, 재귀를 종료한다.

위와 같이 dfs를 통해 탐색하는데, 배열의 현재 원소를 포함(선택)시켜 만드는 부분 수열과, 포함시키지 않고 만드는 부분 수열을 만들어가며, 그 부분수열들의 합이 S가 되는지 확인해야 한다.

특히, S가 0인경우 모든 값의 경우가 0일 때인 공집합일 때를 고려해야 하기에 경우의 수를 출력하기 전 1을 차감해줘야 한다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

class Main {    

    // N개의 수열을 담을 배열 선언
    static int[] arr;
    
    // 수열의 개수 N과 양수인 부분 수열의 개수 S 선언
    static int N, S;

    // 경우의 수를 담을 변수 선언
    static int result;

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

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            
                StringTokenizer st = new StringTokenizer(br.readLine());
                
                N = Integer.parseInt(st.nextToken());
                S = Integer.parseInt(st.nextToken());

                arr = new int[N];

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

                result = 0;

                // dfs 호출하여 탐색을 시작한다.
                dfs(0, 0);

                // 공집합일 경우를 고려해야 하기 때문에 S==0인 경우 경우의 수를 1개 차감한다.
                if(S == 0) {
                    result--;
                }

                bw.write(result+"\n");

        }

    }

    public static void dfs(int depth, int sum) {
        
        // 재귀의 깊이가 N이 된다면 종료한다. 
        if(depth == N) {
            
            // 이때, 부분 수열의 합이 S가 된다면 result를 1 증가시킨다.
            if(sum == S) {
                result++;
            }

            return;

        }
        
        // 원소를 선택했을 경우 sum에 더해여 재귀 호출한다.
        dfs(depth+1, sum + arr[depth]);

        // 원소를 선택하지 않았을 경우 sum을 그대로 재귀 호출한다.
        dfs(depth+1, sum);

    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.