[SWEA] 9229. 한빈이와 Spot Mart

문제

한빈이는 퇴근길에 스팟마트에 들러 과자 두 봉지를 사서 양 손에 하나씩 들고 가려고 한다.

 

스팟마트에는 N개의 과자 봉지가 있으며, 각 과자 봉지는 ai그램의 무게를 가진다.

 

배가 많이 고픈 한빈이는 최대한 양이 많은 (무게가 많이 나가는) 과자 봉지를 고르고 싶으나,

과자 두 봉지의 무게가 M 그램을 초과하면 무거워서 과자를 들고 다닐 수 없다.

 

한빈이가 들고 다닐수 있는 과자들의 최대 무게 합을 출력하라. 한빈이는 과자를 “정확히” 두 봉지 사야 함에 유의하라.

 

풀이방법

한빈이가 가져갈 수 있는 경우의 수를 모두 찾고 이 중 M을 넘지 않는 최대값을 출력한다.

 

한빈이가 가져갈 과자는 2 봉지이므로 DFS(깊이우선탐색)을 사용하지 않아도 이중 반복문으로 구할 수 있다.

 

소스코드

package samsung;

import java.util.*;

public class s_9229 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int test = sc.nextInt();
		
		for(int t = 1; t <= test; t++) {
			int n = sc.nextInt();
			int max = sc.nextInt();
			int[] a = new int[n];
			ArrayList <Integer> l = new ArrayList<>();
			
			for(int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}
			
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					if(i == j)
						continue;
					else {
						int sum = a[i] + a[j];
						if(sum <= max) {
							l.add(sum);
						}
					}
				}
			}
			
			Collections.sort(l, Collections.reverseOrder());
			if(l.size() == 0)
				System.out.println("#" + t + " " + (-1));
			else
				System.out.println("#" + t + " " + l.get(0));
			
		}
	}
}