[SWEA]9229_한빈이와 Spot Mart JAVA 풀이

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

SW Expert Academy

 

 

풀이 :

- 과자 2봉지 중에 제일 무게가 많은 것인데

- 두개의 무게를 합쳐서 M 초과하지 않아야 함

 

* 가지치기 방식으로 풀이

배열로 받아서 정렬하고 큰거 뽑고 아니면 하나씩 인덱스 낮추는 방법 사용

 

그 외에 조합으로 두개 뽑아서 합이 기준을 만족하는 방법도 있을 것 같다.

조합을 아직 잘 다루지 못해서 안했는데 나중에 조합으로도 한번 풀어봐야지

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution_9229 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());
		for(int tc = 1;tc<=TC;tc++) {
		
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken()); // 과자 개수
			int M = Integer.parseInt(st.nextToken()); // 무게 합 제한
			String [] s = br.readLine().split(" ");
			int [] weight = new int[N]; 
			for(int i=0;i<N;i++) {
				weight[i] = Integer.parseInt(s[i]);
			}
			Arrays.sort(weight);
			int max = -1;
			for(int i=N-1;i>0;i--) {
				for(int j=i-1;j>=0;j--) {
					if(weight[i]+weight[j]<=M) {
						if(max< weight[i]+weight[j]) {
							max = weight[i]+weight[j];
						}
						
					}else { 
						continue;
					}
				}
			}
			System.out.println("#"+tc+" "+max);
			
			
		}
	}

}