[백준/14225] 부분수열의 합 - JAVA

📌 문제

알고리즘 분류 : 브루트포스 알고리즘
난이도 : 실버1
출처 : 백준 - 부분수열의 합

🦧 문제 풀이 접근

브루트포스 알고리즘으로 문제를 해결한다.
DFS방식 재귀함수를 통해서 모든 조합의 경우의 수를 구한다.
boolean 배열을 생성하여, 계산된 각각의 경우의 수의 합을 모두 더한 값에 해당하는 인덱스를 true로 설정한다.
boolean 배열에서 가장 작은 false를 반환하는 인덱스를 구한다.

💻 code

import java.util.*;
import java.io.*;
public class Main {
    static boolean[] check = new boolean[2_000_000];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int arr[] = new int[N];
        for(int i=0;i<N;i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int sum=0;
        for(int i=0;i<N;i++) {
            rec(arr,i,N,sum);
        }
        for(int i=1;i<check.length;i++) {
            if(!check[i]) {
                System.out.println(i);
                break;
            }
        }
    }

    private static void rec(int[] arr, int i, int N,int sum) {
        sum+=arr[i];
        check[sum] = true;
        for(int j=i+1;j<N;j++) {
            rec(arr,j,N,sum);
        }
        sum-=arr[i];
    }
}

🥇 결과

🎓 느낀점

재귀함수에 익숙하다면 어렵지 않게 풀 수 있다.