[문제 풀이] 백준 1182번 부분수열의 합 JAVA

문제

 

  문제접근 방법   

해당 문제는 주어진 수열의 부분수열 중에서 원소의 합이 S가 되는 경우의 수를 구하는 프로그램을 작성하는 문제이다.

문제에서 N의 범위가 크지 않기 때문에 모든 수열을 탐색해도 괜찮다고 생각해 아래와 같이 코드를 작성하였다.

 

< 최종 코드  1 >

import java.util.Scanner;

public class Main {
    static int n, s, count;
    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();
        }

        count = 0;
        dfs(0, 0);
        
        if (s == 0) count--;

        System.out.println(count);
    }

   
    static void dfs(int idx, int sum) {
        if (idx == n) {
            if (sum == s) count++;
            return;
        }

        // 현재 원소 포함
        dfs(idx + 1, sum + arr[idx]);
        // 현재 원소 미포함
        dfs(idx + 1, sum);
    }
}

먼저 main함수 내부에서는 수열의 길이와 목표합을 입력받는다. 이후 배열 생성 후 수열 원소를 입력받는다.

그러고 나서 dfs함수를 호출한다. dfs함수에서 종료조건은 if (idx == n)로 모든 원소를 다 확인했다면 종료한다. 

위에도 주석으로 표시해 두었지만

dfs(idx + 1, sum + arr [idx]); == 현재 원소를 포함하는 경우의 탐색

dfs(idx + 1, sum);== 현재 원소를 포함하지 않는 경우의 탐색하는 경우를 의미한다.

결론적으로 각 원소에 대해 포함/비포함을 결정하여 2^n개의 부분집합을 모두 탐색하고 idx == n일 때는 부분수열이 하나 완성된 상태이므로 그 합이 s와 같은지 확인하는 방식이다.

 

해당 문제를 풀이한 후 4개월 후 문제를 다시 풀어보았지만 아래와 같이 같은 구조로 코드를 작성하였다.

< 최종 코드  2 >

import java.util.*;

public class Main{
    public static int arr[];
    public static int cnt=0;
    public static void main(String args[]){
        Scanner ss=new Scanner(System.in);
        
        int n=ss.nextInt();
        int s=ss.nextInt();
        arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=ss.nextInt();
        }
    
            dfs(s,0,0);
        if(s==0)cnt--;
        
        System.out.print(cnt);
    }
    public static void dfs(int s,int start,int sum){
        if(start==arr.length){
            if(s==sum){
            cnt++;
            }
            return;
        }
        
        if(start>arr.length-1)return;
        
        dfs(s,start+1,sum+arr[start]);
        dfs(s,start+1,sum);    
        
    }
}

다만 이번에도 풀이할 때와 이전 풀이할 때에 공통적으로 놓친 부분이 있어서 정리해보려 한다.

이전 풀이에서 언급하였듯이 해당 문제에서 핵심은 dfs를 활용하여 분기를 나누어주는 것이라고 생각한다.

선택한다와 선택하지 않는다는 것을 dfs를 2번 호출해서 나누는 것이다. 

하지만 이외에도 고려해야 할 점이 하나 더 있는데 그것은 바로 공집합이다. 문제에서 s가 0일 경우 

아무것도 선택되지 않았을 때의 공집합과 요소의 합이 0인 경우가 같이 카운트될 경우가 존재해 이를 고려해서 코드를 작성해야 한다. 이번에도 이를 고려하지 못했고 저번에도 고려하지 못했다. 조금 더 문제를 자세하게 분석할 필요에 대해 느끼게 되었다.