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

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

 

 

 

부분수열의 합

 

 

1)  문제

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

입력: 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력: 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

 

 

2)  예시

예제입력 1:

5 0
-7 -3 -2 5 8

예제출력 1: 

1

 

3)  풀이

* 아이디어
1. 모든 부분수열을 탐색해야 하므로 → 부분집합 문제
    → 각 원소를 “고를지 / 안 고를지”의 두 가지 선택으로 분기

2. DFS 재귀를 이용해 모든 조합을 탐색
    → dfs(index + 1, sum + arr[index]) (현재 원소 선택)
    → dfs(index + 1, sum) (현재 원소 미선택)

3.  합이 목표값 S와 일치하는 경우만 count 증가
공집합은 제외해야 하므로 S == 0일 경우 count-- 처리 필요 (선택을 아무것도 안 한 경우)

 

 

 

4)  코드

import java.util.Scanner;
// Scanner 클래스를 불러옴

public class Main {
// 자바 시작점인 클래스_ 백준에서는 Main으로 정의해야함
    static int N, S, count;
    // 수열의길이N, 목표로하는 부분수열합 S, 조건에맞는경우의수count 변수
    static int[] arr;
    // 입력받은 수열을 저장한 정수배경

    public static void dfs(int index, int sum) {
    // dfs 메소드 정의, index는 현재 탐색중인 배열위치, sum은 지금까지 선택한 숫자의합
        if (index == N) {
        // 모든 원소를 탐색했을 때(배열 끝에 도달했을때)
            if (sum == S) {
                count++;
            }
            // 현재까지 구한 수열의합이 목표값인 S와 같을 경우 count 1증가 (정답을 세는 조건)
            return;
        }

        // 현재 숫자를 포함하는 경우
        dfs(index + 1, sum + arr[index]);
        // 인덱스를 1 증가시키고, 해당 값을 sum에 더해서 다음 DFS로 진행

        // 현재 숫자를 포함하지 않는 경우
        dfs(index + 1, sum);
        // sum은 그대로 유지한 채 다음 인덱스로 진행
    }

    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);
        // index = 0부터 시작, 현재 합은 0


        // 공집합 제외
        if (S == 0) count--;
        // 아무것도 선택하지 않은 경우에도 sum == 0일 수 있음
        // 하지만 문제는 “공집합은 제외”라고 명시했기 때문에
        // S == 0일 때 count에서 1을 빼줌

        System.out.println(count);
    }
}

 

 

 

 

 

 

 

 

 

5)  리뷰

공집합의 경우 합이 0이 될 수 있어서 예외 처리를 해줘야 한다는 조건이 기억에 남는다.

재귀 흐름이 익숙하지 않은 상태였지만, 호출 순서를 하나씩 따라가다 보니
부분집합을 탐색하는 기본 패턴을 체득할 수 있는 좋은 연습 문제였다.