SWEA 9229 한빈이와 SpotMart

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW8Wj7cqbY0DFAXN 

SW Expert Academy

 

 

문제)

 

 

풀이)

이 문제는 조합으로 풀면 괜찮게 풀린다.

사실 조합코드를 짜기가 조금... 귀찮아서 어차피 2개만 뽑는 것이니 for문 2개를 이용해서 풀었다.

두 개의 간식을 더하고, 그것이 경계를 넘지 않으면서 최대값을 찾는 과정을 반복한다!

 

import java.util.Scanner;
//import java.io.FileInputStream;

class Solution_D3_9229_한빈이와SpotMart{
	public static void main(String args[]) throws Exception{
		//System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			int N = sc.nextInt();
			int M = sc.nextInt();
			int[] snack = new int[N];
			for(int i=0; i<N; i++) {
				snack[i]=sc.nextInt();
			}
			
			int answer = 0;
			int temp = 0;
			
			
			for(int i=0; i<N-1; i++) {
				for(int j=i+1; j<N; j++) {
					temp = snack[i]+snack[j];
					if(temp<=M && answer<temp) {
						answer = temp;
					}
				}	 
			}
			
			if(answer == 0) {
				answer = -1;
			}
			
			
			System.out.println("#"+test_case + " " + answer);
			
		}
		sc.close();
	}
}

 

 

조합으로 짠 코드!!

시간은 더 오래 걸린다.

import java.util.Scanner;
//import java.io.FileInputStream;

class Solution_D3_9229_한빈이2{
	
	static int[] snack;
	static int N, M, answer;
	static boolean[] v;
	public static void comb(int start, int cnt) {
		if(cnt == 2) {
			cal();
			return;
		}
		
		for(int i=start; i<N; i++) {
			if(v[i])
				continue;
			
			v[i]=true;
			comb(i+1, cnt+1);
			v[i]=false;
			
		}
	}
	
	public static void cal() {
		int sum=0;
		for(int i=0; i<N; i++) {
			if(v[i])
				sum+=snack[i];
		}
		if(sum<=M)
			answer = Math.max(answer, sum);
	}
	
	public static void main(String args[]) throws Exception{
		//System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			N = sc.nextInt();
			M = sc.nextInt();
			snack = new int[N];
			//과자 무게 기록 
			for(int i=0; i<N; i++) {
				snack[i]=sc.nextInt();
			}
			
			v=new boolean[N];
			answer = 0;
			comb(0, 0);
			
			if(answer == 0) {
				answer = -1;
			}
			
			System.out.println("#"+test_case + " " + answer);
			
		}
		sc.close();
	}
}