[swea-D4] 3752. 가능한 시험 점수

# [swea-D4] 3752. 가능한 시험 점수

🙋‍♂️ 들어가며

조건을 잘 읽어보자

1 <= N <= 100

이라서 조합을 쓰게 되면 100 C 50 이 되므로 시간초과.

하지만 혹시나하는 마음에 조합 코드를 짜보았고 시간초과로 실패했다

그래서 이후 DP 부분집합을 작성하니 통과하였다

❌ 틀린 코드 (조합)

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



public class Solution {
	static int N;
	static boolean[] visited;
	static int cnt;
	static int[] arr;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc < T+1; tc++) {
			N = Integer.parseInt(br.readLine());
			String[] s = br.readLine().split(" ");
			
			
			// 1. 배열 생성
			int size = 0;
			arr = new int[N];
			for (int i = 0; i < N; i++) {
				arr[i] = Integer.parseInt(s[i]);
				size += arr[i]; 
			}
			
			// 2. 조합 (0점을 추가하기위해 cnt++)
			cnt = 0;
			cnt++;
			visited = new boolean[size + 1];
			int cur_sum = 0;
			for (int i = 0; i < N; i++) {
				int idx = i;
				comb(idx+1, cur_sum + arr[idx]);
			}
			
			// 4. 출력
			System.out.println("#" + tc + " " + cnt);
		}
	}
	
	
	// 3. 조합 함수
	static void comb(int start_idx, int cur_sum) {
		// 3-1. 최대깊이 도달시
		if (start_idx == N) {
			if (!visited[cur_sum]) {
				visited[cur_sum] = true;
				cnt++;
			}
			return;
		}
		
		// 3-2. 최대깊이 도달 안했어도 -> 방문 안했으면 횟수 추가
		if (!visited[cur_sum]) {
			visited[cur_sum] = true;
			cnt++;
		}
		
		// 3-3. 그 외 조합 진행
		for (int i = start_idx; i < N; i++) {
			int idx = i;
			comb(idx+1, cur_sum + arr[idx]);
		}
	}
	
	
	
	
	
}

✅ 정답 코드

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



public class Solution {
	static int N;
	static boolean[] DP;
	static int cnt;
	static int[] arr;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc < T+1; tc++) {
			N = Integer.parseInt(br.readLine());
			String[] s = br.readLine().split(" ");
			
			
			// 1. 배열 생성
			int size = 0;
			arr = new int[N];
			for (int i = 0; i < N; i++) {
				arr[i] = Integer.parseInt(s[i]);
				size += arr[i]; 
			}
			
			// 2. 0점을 추가하자
			DP = new boolean[size + 1];
			DP[0] = true;
			
			
			// 3. 다른 부분집합 계산
			for (int i = 0; i < N; i++) {
				int cur_score = arr[i];
				for (int j = size; cur_score; j >= 0; j--) {
					// 3-1. 이미 점수가 기록되어있으면
					if (DP[j]) {
						DP[cur_score + j] = true;
					}
				}
			}
			
			
			// 4. 출력
			int cnt = 0;
			for (int i = 0; i < size+1; i++) {
				if (DP[i]) cnt++;
			}
			System.out.println("#" + tc + " " + cnt);
			
				
		}
	}
}