이번에 풀어본 문제는
백준 14225번 부분수열의 합 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

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

        sum = new boolean[size+2];

        for(int i = 0; i < N; i++)
        {
            comb(i,map[i]);
        }

        for(int i = 1; i < size+2; i++)
        {
            if(!sum[i])
            {
                System.out.print(i);
                break;
            }
        }
    }
    static void comb(int idx, int tmp)
    {
        sum[tmp] = true;
        for(int i = idx+1; i < N; i++)
        {
            comb(i,tmp+map[i]);
        }
    }
}

📝 풀이

주어진 수열의 부분수열의 합이 될 수 없는 자연수중 최솟값을 구하는 문제입니다.
부분수열의 합을 모두 구하고, 1부터 시작하는 자연수들 중 구해지지 않은 값을 출력하면 해결할 수 있습니다.
부분수열의 합은 조합을 이용하여 구하면 됩니다.

📜 후기

부분수열로 만들 수 있는 최댓값까지 전부 구할 수 있는 경우가 있다는 것을 인지해야합니다. ex) (2,1,4)