SWEA 3752. 가능한 시험 점수 :: 돼지개발자

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

"구현... 다시보자! 꾸에에에엑"

다시보자... 왜 이런 생각을 못했을까. 처음에 그냥 브루트 포스로 전체 경우의 수를 재귀로 다 돌려보았다. 시간 초과.

풀이 참고해서 풀었따. 알고리즘은 아래와 같다. 

1. 각 배점을 받을 때마다 최대값을 갱신한다.

2. 갱신된 최대값 ~ 0 까지 탐색하며, 만약 이전에 이미 맞았던 점수가 있다면 이 점수에 내가 방금 입력받은 점수를 더해준 값도 체크한다.

3. true 로 체크된 값들의 개수를 센다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    static int T;
    static int N;
    static boolean[] visited;
    static int[] map;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        T = Integer.parseInt(br.readLine());
        
        int t = 1;
        while(T-- >0) {
            N = Integer.parseInt(br.readLine());
            map = new int[N];
            visited = new boolean[100001];
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            int max = 0;
            int res = 0;
            
            visited[0] = true;
            for (int i = 0; i < N; i++) {
                map[i] = Integer.parseInt(st.nextToken());
                max += map[i];
                
                for (int j = max; j >= 0; j--) {
                    if(visited[j])
                        visited[j + map[i]] = true;
                }
                visited[map[i]] = true;
            }
            for (int i = 0; i <= max; i++) {
                if(visited[i]) res++;
            }
            System.out.printf("#%d %d\n",t++,res);
        }
    }
}