SWEA- 9229 한빈이와 Spot Mart

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW8Wj7cqbY0DFAXN#;return%20false;

SW Expert Academy

---

맞게 풀었는데 시간초과가 나서 당황했던 문제  

완전 탐색으로 풀 경우 시간초과가 터지면 가지치기를 하는게 시간을 최소화시킬 수 있다.

---

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class 한빈이와SpotMart {
	static int N,M,ans;
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input/swea_9929.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			ans=-1;
			N =sc.nextInt();//과자의개수
			M = sc.nextInt();//제한 무게
			int []snack = new int [N];
			for (int i = 0; i < N; i++) {
				snack[i]=sc.nextInt();
			}
			combination(snack,new int[2],0,0);
			
			System.out.printf("#%d %d\n",tc, ans);
		}
	}
	private static void combination(int [] snack, int[] sel, int idx, int k) {
		if(k==sel.length) {
			int Msum=0;
			for (int i = 0; i < 2; i++) {
				Msum+= sel[i];
			}
			//System.out.println(Arrays.toString(sel));
			if(Msum>M) {return;}
			if(Msum<=M) {
				ans =Math.max(ans, Msum);
				return;
			}
			//시간이 오래걸릴땐 가지치기를 하자!
	
		}
		
		for (int i = idx; i < N; i++) {
			sel[k]=snack[i];
			combination(snack, sel, i+1, k+1);
			
		}
	}

}