[코드트리] 부분 수열의 합(DP)

문제

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-the-sum-of-the-subsequences/

 

 

입출력

 

 

 

---

아이디어

 

 

N개의 원소 A 내 부분 수열의 합이 M이 되는 경우가 있는지 판단 

DP[i][j] : i번째 원소까지 고려할 때 부분 수열의 합이 j가 될 수 있음

1) 부분 수열에 포함시키는 경우

2) 포함시키지 않는 경우 

코드 

 

import java.io.*;
import java.util.*;
public class Main {
    static int N, M;
    static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        arr = new int[1000];
        for(int i = 0; i < N ; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        // dp[i][j] : i번째 원소까지 고려할 때 부분 수열의 합이 j가 될 수 있음 
        // 1. 부분 수열에 포함시키는 경우 
        // 2. 포함시키지 않는 경우 
        boolean[][] dp = new boolean[1000+1][100+1];
        dp[0][0] = true;
        // 지금까지 i번째 수까지 고려 O
        // 지금까지 고른 수들의 합이 j가 되는게 가능?
        for(int i = 1; i <= N; i++){
            // i번 수를 선택하여 합이 j가 된 경우
            // j >= arr[i] && dp[i-1][j-arr[i]]
            for(int j = 0; j <= M; j++){
                if(j >= arr[i] && dp[i-1][j-arr[i]]){
                    dp[i][j] = true;
                }
                // i번 수를 선택하지 않고 합이 j가 된 경우
                // dp[i-1][j]
                if(dp[i-1][j]){
                    dp[i][j] = true;
                }
            }
        }

        if(dp[N][M]){
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}