코드트리 [자바 java] 부분수열의 합이 m

https://www.codetree.ai/missions/2/problems/the-sum-of-the-subsequences-is-m?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

이 문제는 동전문제와 비슷하다. 하지만 이 문제에서 유의할 점은 동전을 오직 한번만 사용해야한다는 것이다.

이를 위해 합으로 만들어야 하는 수만큼 dp 값을 만들고, 뒤에서부터 탐색을 진행한다. 순서는 상관이 없으니 고려하지 않는다. 

 

0

10000

10000

10000

10000

10000

여기서 만약 2로 앞에서부터 탐색한다면, 

0

10000

1

10000

2

10000

이런식으로 중복돼서 사용되는 경우도 포함되어 오류가 발생한다.

 

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

public class Main {
   

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());


        for(int i = 0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[m+1];

        for(int i = 1;i<=m;i++){
            dp[i] = 100000;
        }

        for(int i = 0;i<n;i++){
            for(int j = m;j>=1;j--){
                if(j - arr[i] >= 0){
                    dp[j] = Math.min(dp[j],dp[j-arr[i]]+1);
                }
            }
        }

        if(dp[m] == 100000) System.out.println(-1);
        else System.out.println(dp[m]);

        
    }
}