테스트 코드 96

import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Solution { static int N, M; static int[] A; static boolean[] D; public static void main(String[] args) throws IOException { //System.setIn(new FileInputStream("res/inputPre07.txt")); // System.setIn(new FileInputStream("res/sample_input_Pre07.txt")); long Start = System.currentTimeMillis(); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine()); StringTokenizer st; for (int t = 1; t < T+1; t++) { st = new StringTokenizer(br.readLine(), " "); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); A = new int[M+1]; D = new boolean[1000001]; int id = 0; int result = -1; ArrayList<Integer> ol = new ArrayList<Integer>(1001); ArrayList<Integer> el = new ArrayList<Integer>(1001); int n; for (int i = 1; i < M+1; i++) { n = Integer.parseInt(st.nextToken()); if(n == N) { result = 1; break; } else if(!D[n]) { D[n] = true; A[id++] = n; ol.add(n); } } if(result < 0) { ArrayList<Integer> cl, nl; int LN, RN, NN; int temp; for (int i = 2; i < 1001; i++) { cl = ((i%2)==0)?ol:el; nl = ((i%2)==1)?ol:el; NN = (N*i); LN = NN-2000; RN = NN+2000; for (Integer num : nl) { D[num] = false; } for (Integer num : cl) { for (int j = 0; j < id; j++) { temp = num + A[j]; if((LN>temp) || (RN<temp)) continue; else if(temp==NN) { result = i; } else { if(!D[temp]){ nl.add(temp); D[temp] = true; } } } if(result > 0) break; } cl.clear(); if(result > 0) break; } } System.out.println("#"+t+" "+result); } //System.out.println("total : " + (System.currentTimeMillis()-Start)+ " ms"); } }