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

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn 

SW Expert Academy

풀이

처음에는 백트레킹을 이용하여 모든 값을 set에 넣고 set의 사이즈를 구하려고 했다.

그러나, 시간초과가 발생하여 다른 경우를 탐색해보았다.

 

문제를 자세히 탐색해보면 규칙이 발생했다. 

 

만약 N이 1이고 배점이 A라면

N=1 : 0,  A

배점이 A, B 라면

N=2 : 0, A, B, A+B

배점이 A, B, C 라면

N=3 : 0, A, B, A+B, C, A+C, B+C, A+B+C

 

즉, 이전의 원소들에서 새로운 배점이 추가되면 기존 원소들을 유지되며 기존 원소들에 대해 새로운 배점이 더해진다.

그렇다면, 이를 어떻게 구현해야 할까?

HashSet을 이용하면 중복되는 것이 제거되기 때문에 HashSet을 이용한다.

또한, Set에서 값을 가져오기 위해 Iterator를 이용해야 한다.

Iterator를 이용하여 값을 가져오고 다시 저장해야 하는데 Iterator가 사용된 HashSet에는 저장을 못하기 때문에 HashSet의 copy본을 만들고 그것에 Iterator를 적용시키고 값 저장은 원본 HashSet에 한다.

코드

import java.util.*;
import java.io.*;

class Solution {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
				
		int T = Integer.parseInt(br.readLine());
		for(int test_case = 1; test_case <= T; test_case++)
		{			
			int n = Integer.parseInt(br.readLine());
			int arr [] = new int [n];
			HashSet<Integer> hashSet = new HashSet<>();
			
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<n;i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
					
			for(int i=0;i<n;i++) {
				HashSet<Integer> copy = new HashSet<>();
				copy.addAll(hashSet);
				Iterator<Integer> it = copy.iterator();
				while(it.hasNext()) {
					hashSet.add(it.next()+arr[i]);
				}
				
				hashSet.add(arr[i]);				
			}
			
			System.out.println("#"+test_case+" "+(hashSet.size()+1));

		}
		
	}
	
}