[SWEA]#3752 가능한 시험 점수

문제

영준이는 학생들의 시험을 위해 N개의 문제를 만들었다.

각 문제의 배점은 문제마다 다를 수 있고, 틀리면 0점 맞으면 배점만큼의 점수를 받게 된다.

학생들이 받을 수 있는 점수로 가능한 경우의 수는 몇 가지가 있을까?

예를 들어, 첫 번쨰 Testcase의 경우, 총 문제의 개수는 3개이며 각각의 배점은 2, 3, 5점이다

가능한 시험 점수의 경우의 수를 살펴보면 0, 2, 3, 5, 7, 8, 10의 7가지가 있다.

두 번째 Testcase의 경우, 총 문제의 개수는 10개이며 각각의 배점은 모두 1점이다.

가능한 시험점수의 경우의 수를 살펴보면 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10으로 모두 11가지이다.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 자연수 N(1 ≤ N ≤ 100)이 주어진다.

두 번째 줄에는 각 문제의 배점을 의미하는 N개의 자연수가 공백으로 구분되어 주어진다. 배점은 1이상 100이하의 자연수이다.

출력

각 테스트 케이스마다 학생들이 받을 수 있는 점수의 경우의 수를 출력한다.

예제 입력

2           //Test Case 수
3           //Test Case 1, N = 3
2 3 5
10
1 1 1 1 1 1 1 1 1 1	

예제 출력

#1 7    //Test Case 1의 정답
#2 11	   //Test Case 2의 정답

풀이

이 문제는 DFS알고리즘과 DP알고리즘을 사용해서 풀 수 있는 문제이다.

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

class Solution {
    static int[] arr;
    static boolean[][] visited;
    static int N;
    
	public static void main(String args[]) throws IOException{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		  int T = Integer.parseInt(br.readLine());
	
		  for(int test_case = 1; test_case <= T; test_case++) {
            N = Integer.parseInt(br.readLine());
            String[] input = br.readLine().split(" ");
            arr = new int[N];
            int sum = 0;
            
            for(int i=0; i<N; i++) {
                arr[i] = Integer.parseInt(input[i]);
                sum += arr[i];
            }
            visited = new boolean[N+1][sum+1];
            dfs(0, 0);
            int ans = 0;
            for(int i=0; i<=sum; i++) {
                if(visited[N][i])
                    ans++;
            }
            System.out.println("#"+test_case+" "+ans);
		  }
	  }
    
    public static void dfs(int idx, int sum) {
        if(visited[idx][sum]) return;  
        visited[idx][sum] = true;
        if(idx>=N) return;
        
        dfs(idx+1, sum+arr[idx]);
        dfs(idx+1, sum);
    }
}