문제

문제 바로가기

풀이

• 처음에는 모든 경우의 수를 탐색하면서 Set에 추가하여 풀었지만 시간초과.

  • 문제는 최대 100가지 이므로, 경우의 수는 2^100 이고 당연히 시간 초과가 발생한다.

• DP를 사용하여 문제 해결

  • 각 배점을 탐색하면서 만들 수 있는 경우의 수를 DP에 기록
  • 해당 배점을 선택하기 이전까지 DP배열에 기록된 모든 값들 + 현재 탐색중인 배점을 DP 배열에 기록
  • 위의 방식대로 계속해서 배점 탐색

• 최종적으로 DP 배열에 기록된 갯수를 출력

코드

import java.util.*;
// dp로 탐색
// 최대 점수만큼의 크기를 가지는 dp 배열 생성
// 1. 한 문제씩 선택
// 2. 해당 문제를 dp배열에 기록
// 3. 지금 까지 기록된 dp배열에 선택된 문제를 더한 값도 dp에 기록
// 4. 계속 문제 선택하면서 진행

class Solution{    
	static public void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int T;
        T = sc.nextInt();
        
        for (int test_case = 1; test_case <= T; test_case++){
            // Input
        	int n = sc.nextInt();
            int maxVal = 0;
            int[] arr = new int[n];
            for(int i = 0; i < n; i++){
            	arr[i] = sc.nextInt();
                maxVal += arr[i];
            }
            
            // 탐색
            int[] dp = new int[maxVal+1];
            dp[0] = 1;
            for (int point : arr){
                int[] temp = dp.clone();	// dp 탐색하면서 업데이트 한 값이 반영되지 않도록 임시 배열에서 업데이트
                for (int i = 1; i <= maxVal; i++){
                	if (dp[i] == 1 && i+point <= maxVal){
                        temp[point + i] = 1;
                    }
                }
                dp = temp;
                dp[point] = 1;
            }            
            
            // 갯수 계산
            int answer = 0;
            for (int selected : dp){
            	if (selected == 1)		answer+=1;
            }
            
            // 출력
            System.out.printf("#%d %d\n", test_case, answer);
        }
    }
}

실행 결과