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

링크

SWEA[4014]

문제설명

• -

문제풀이

• 경우의 수

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution3752 {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/swea/3752.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim()," ");

        int T=Integer.parseInt(st.nextToken());
        for (int test_case = 1; test_case <= T; test_case++) {
            int ans=0;
            int [] index = new int [10001];
            int [] temp_index = new int[10001];
            st = new StringTokenizer(br.readLine().trim()," ");
            int N = Integer.parseInt(st.nextToken());
            int[] score = new int[N];

            st = new StringTokenizer(br.readLine().trim()," ");
            for (int i = 0; i < N ; i++) {
                score[i] = Integer.parseInt(st.nextToken());
            }

            int idx_max=0;
            int max = idx_max+1;
            index[0]=1;

            for (int i = 0; i < N; i++) {
                for (int idx = 0; idx < max; idx++) {
                    if(index[idx]!=0) {
//                        System.out.println(idx+score[i]);
                        temp_index[idx+score[i]]++;
                        idx_max = Math.max(idx_max, idx+score[i]);
                        int debug=0;
                    }
                }
                max = idx_max+1;
                for (int idx = 0; idx < max; idx++) {
                    if(temp_index[idx]!=0) {
                        index[idx]=temp_index[idx];
                        temp_index[idx]=0;
                    }
                }
                int debug=0;
            }

            for (int i = 0; i < 10001; i++) {
                if(index[i]!=0)ans++;
            }
            System.out.println("#"+test_case+" "+ans);
            /*
             * 초기화
             */
        }//end test_case
    }//end main
}

아쉬운점

• stack으로 시도했었다가 시간초과뜸
• 5 2 3 경우 5추가되고 5까지 탐색하는데 2,4,6 이렇게 추가되는 경우 있음
  • array 하나 더 생성해서 해야 함

잘한점

• sum MAX가 10000임을 이용하고 index를 이용해서 해결