[swexpert] 3752. 가능한 시험점수 (java, dfs, 완전탐색, 구현)

백준의 양팔 저울과 문제가 같은 문제인거 같다. 

부분합으로 구할 수 있지만 시간초과가 나서 시간을 줄이기 위해서 이전까지 나온 결과값에 현재 점수를 더해주면서 

set과 arr 리스트를 갱신해줬다. 

 

arr배열을 만든 이유는 현재 점수를 틀렸다고 가정했을 때 이전 점수와 같은 점수가 될 텐데 또 더해주지 않으면서 

다음 문제 차례에 계산할 때 쓸 이전 점수들의 모음이 필요하기 때문이다.

 

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Solution {
	static int n,t;
	static int[] score;
	static Set<Integer> s;
	static ArrayList<Integer> arr;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		t=sc.nextInt();
		for (int tc = 1; tc <=t; tc++) {
			n=sc.nextInt();
			score=new int[n];
			arr=new ArrayList<>();
			for (int i = 0; i < n; i++) {
				score[i]=sc.nextInt();
			}
			s=new HashSet<>();
			s.add(0);
			arr.add(0);
			check(0);
			System.out.printf("#%d %d\n",tc,s.size());
		}
	}
	private static void check(int cnt) {
		if(cnt==n) {
			return;
		}
		int len=arr.size();
		for (int i = 0; i < len; i++) {
			if(!s.contains(arr.get(i)+score[cnt])) {
				s.add(arr.get(i)+score[cnt]);
				arr.add(arr.get(i)+score[cnt]);
			}
		}
		check(cnt+1);
	}
}