[백준/Java] 1182번 : 부분 수열의 합

✏️ 문제 분석

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

N개의 정수로 이루어진 수열의

부분 수열의 원소를 모두 더한 값이 S가 되는 경우의 수를 구하라.

✏️ 구현 아이디어

부분 수열의 원소를 더한 값이 S가 되는지 판단하려면

브루트 포스로 모든 부분 수열을 구한 후 직접 더해봐야 한다.

 

🤔 모든 부분 수열을 구하는 방법?

N개의 원소 각각을 선택하든가, 선택하지 않든가

둘 중 하나의 경로를 선택하는 것을 반복하여

재귀탐색을 하면 된다!

 

dfs와 동일한 방법이다.

N개의 원소를 가진 수열 N개를 dfs 탐색하는 것과 같다.

 

• 첫 번째 원소
  • 선택함 
  • 선택하지 않음 
  • 두 번째 원소를 선택하러 재귀탐색
• 두 번째 원소
  • 선택함
  • 선택하지 않음
  • 세 번째 원소를 선택하러 재귀탐색

...

이런 식으로 N번째 원소까지 반복하면 모든 부분 수열이 만들어진다.

그리고 depth가 N에 도달하였을 때, 만들어진 부분 수열의 모든 원소의 합을 구해 S와 같으면 개수를 하나 카운트한다.

✏️ 시간 복잡도

1번째 부터 N번째 원소까지 재귀 탐색 : O(N)

원소를 선택/미선택 : O(2)

원소의 합이 S인지 확인 : O(1)

 

따라서 전체 시간 복잡도는 O(2N)이다.

N은 최대 20이므로 시간 안에 연산 가능하다.

✏️ 알고리즘

브루트 포스

✏️ 코드 설계

1. 입력값 받기
2. dfs를 수행
   1. N개의 원소를 선택하는 경우, 선택하지 않는 경우로 나누어 재귀탐색
   2. depth가 N이 되었으면 부분 수열 합이 S인지 확인하고, 일치하면 cnt++
3. cnt를 출력한다.

✏️ 정답 코드

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


public class Main {
    static int[] arr;
    static int N, S, cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());
        }

        dfs(0, 0);
        if(S==0) cnt--; //S가 0일 때는 if(sum==S)에서 sum이 0일 때 하나 더 카운트 되므로 1 빼줘야 함
        System.out.println(cnt);
    }

    static void dfs(int depth, int sum){
        if(depth==N) {
            if(sum==S)
                cnt++;
            return;
        }
        dfs(depth+1, sum+arr[depth]); //원소를 선택하는 경우
        dfs(depth+1, sum); //원소를 선택하지 않는 경우
    }
}