[SW Experts Academy] 3752. 가능한 시험점수 - (JAVA풀이)

<서론>

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

정답 코드는 결론에..

위 링크는 문제 링크이다.

D4를 다 풀어보자! 라는 마인드로 D4문제를 풀고 있는데, 음.. 아직까지는 조금 쉬운 느낌이다. D5로 올려서 풀어야하나. 암튼 제출이 많은 순서대로 문제를 풀어보기로 했다! 그 중 첫번째가 바로 "3752 가능한 시험점수" 이다!

---

 

 

<본론>

처음 문제를 접했을 때, 이건 모든 경우를 다 구해서 set에 넣고 set의 사이즈를 구하면 되지 않을까 했다. 그리고 모든 경우를 combination 풀 듯 구해볼까 했다.

그런데..

만약 문제의 수가 최대 100개일때, 100 C 50은 어마어마한 경우의 수가 나오는 것이었다. 결국 다른 방법으로 풀어야겠다 생각하고 고민..

아무리 고민해봐도 이 문제는 모든 경우를 다 구해서 set에 넣는게 맞는 것 같았다. 그래서 모든 경우를 조금 다르게 구해보려 했다.

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

N=1 :0,  A

요렇게 2개가 나올 것이다. 근데 만약 여기서 B가 추가된다면?

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

이렇게 2개가 더해져 4개의 결과가 나왔다. C까지 추가된다면?

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

이렇게 4개가 더해져 8개가 되었다!

그렇다! 느낌 왔다! 문제가 x개 라면, x-1개 일때의 모든 경우의 수에 +x번째 수를 더한만큼 더 있으면 되는 것이었다!

중복값이 생겨도, set에 들어가면 중복이 제거되니 저런 식으로 구하고 set에 add만 해주면 되었다!

처음에 조금 생각을 했지만, 결국 금방 풀 수 있었다!

---

 

 

<결론>

SET은 중복을 허용하지 않는다.

N	경우의 수
N = 1 // A	0, A
N = 2 // A, B	0, A, 0+B, A+B
N = 3 // A, B, C	0, A, B, A+B, 0+C, A+C, B+C, A+B+C
...	...

import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;
 
public class Solution {
 
    static Set<Integer> set = new HashSet<Integer>();
    
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        int T = sc.nextInt();
        for (int test_case = 1; test_case <= T; test_case++) {
            set.clear();
            int ans = 0;
            int N = sc.nextInt();
            int[] qArray = new int[N];
            set.add(0);
            for (int i = 0; i < N; i++) {
                qArray[i] = sc.nextInt();
            }
            
            for(int i=0; i<qArray.length; i++) {
                scoreSelect(qArray[i]);
            }
            
            ans = set.size();
            System.out.println("#" + test_case + " " + ans);
        }
        sc.close();
    }
    
    static void scoreSelect(int num) {
        Set<Integer> tmpSet = new HashSet<Integer>(); 
        tmpSet.addAll(set);
        Iterator<Integer> it = tmpSet.iterator();
        while(it.hasNext()) {
            set.add(it.next()+num);
        }
    }
}