SWEA 3752 - 가능한 시험 점수 [Java]

문제

SW Expert Academy

풀이

놀랍게도 장훈이의 높은 선반 문제와 완전히 똑같은 문제다.

import java.util.*;
 
public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            int N = sc.nextInt();
            int[] arr = new int[N];
            int total = 0;
            for (int i = 0; i < N; i++) {
                arr[i] = sc.nextInt();
                total += arr[i];
            }
            Arrays.sort(arr);
             
            boolean[] dp = new boolean[total+1];
            dp[0] = true;
             
            for (int num: arr) {
                for (int i = total; i >= num; i--) {
                    if (dp[i - num]) dp[i] = true;
                }
            }
             
            int answer = 0;
            for (int i = 0; i < total+1; i++) {
                if (dp[i]) answer++;
            }
             
            System.out.println("#" + tc + " " + answer);
             
        }
         
        sc.close();
    }
}