알고리즘 풀이 - 백준 14225(부분수열의 합, 완전 탐색)

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

수열 S가 주어질 때, 수열 S의 부분 수열의 합으로 불가한 자연수 중 가장 작은 수를 구하는 문제

 

 

2. 풀이

 

완전 탐색을 통해 주어진 모든 숫자들의 합을 다 시도하고 그 중 나오지 않은 가장 작은 자연수를 출력하는 문제이다.

재귀 또는 비트마스크, 순열 등 완전 탐색의 갖은 방법으로 문제를 해결할 수 있지만 아래에선 재귀 , 비트마스크만 사용하였다.

 

① 재귀로 풀기

재귀를 통해 다음 탐색할 index값을 전달하여 현재 사용되지 않은 숫자들을 더할 때마다 그 결과를 boolean 배열에 저장하여 문제를 해결한다.

 

② 비트마스크로 풀기

숫자가 3개라면 총 000 ~ 111까지 비트로 표시할 수 있다. 1은 덧셈에 사용할 숫자, 0은 아닌 경우로 지정하여 모두 탐색한 뒤 1인 경우에 각 숫자를 더하고 그 결과를 boolean 배열에 저장하여 문제를 해결한다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

① 재귀로 풀기

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

public class Main{
    static int n;
    static int[] s;
    static boolean[] used = new boolean[2000001];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        s = new int[n];

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

        for(int i=0; i < n; i++){
            recursive(i, s[i]);
        }

        int ans = 0;
        for(int i=1; i < used.length; i++){
            if(!used[i]) {
                ans = i;
                break;
            }
        }
        System.out.println(ans);
        br.close();
    }

    private static void recursive(int idx, int num){
        used[num] = true;
        for(int i=idx+1; i < n; i++){
            recursive(i, num + s[i]);
        }
    }
}

 

② 비트마스크로 풀기

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

public class Main{
    static int n;
    static int[] s;
    static boolean[] used = new boolean[2000001];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        s = new int[n];

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

        for(int i=0; i < (1 << n); i++){
            int sum = 0;
            for(int j=0; j < n; j++){
                if((i & (1 << j)) != 0){
                    sum += s[j];
                }
            }
            used[sum] = true;
        }

        int ans = 0;
        for(int i=1; i < used.length; i++){
            if(!used[i]) {
                ans = i;
                break;
            }
        }
        System.out.println(ans);
        br.close();
    }

}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.