9229. 한빈이와 Spot Mart - 자바(JAVA)

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

SW Expert Academy

 

문제 해석

마트에는 N개의 과자 봉지가 있으며, 각 과자 봉지는 a(i) 그램의 무게를 가집니다.

최대한 많은 과자 봉지를 고르고 싶으나 과자 두 봉지의 무게가 M 그램을 초과하면 무거워서 들고 다닐 수 없습니다.

단, 과자는 정확히 두 봉지 사야 합니다.

들고 다닐 수 있는 과자들의 최대 무게 합을 출력하세요.

 

입력

첫 번째 줄에 테스트 케이스의 수 TC 가 주어진다.

 

이후 TC 개의 테스트 케이스가 새 줄로 구분되어 주어진다. 각 테스트 케이스는 다음과 같이 구성되었다.

첫 번째 줄에 과자 봉지의 개수와 무게 합 제한을 나타내는 자연수 N, M이 주어진다.

 

이후 N개의 줄에 각 과자봉지의 무게가 주어진다.

 

출력

각 테스트 케이스마다 ‘#x’(x는 테스트 케이스 번호를 의미, 1부터 시작)를 출력하고,

한빈이가 들고 갈 수 있는 과자 봉지의 무게 합 최대를 출력하라.

만약 한빈이가 두 과자를 들고 갈 방법이 없는 경우에는 -1을출력한다.

 

 

문제 풀이 전 설계

최악의 경우 1000개 중에 과자 중 2개를 뽑는 조합 중 최대 무게를 넘지 않는 선에서 들 수 있는 무게를 선택해야 합니다.

 

반복문으로도 해결할 수 있지만 조합(Combination)을 재귀적으로 구현해 보았습니다.

 

 

코드

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

public class Solution_9229_한빈이와SpotMart {

	static int snackCount, weightLimit;
	static int result=-1;
	static int snackWeightArray[];
	static int num[] = new int[2];
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		
		for (int t = 1; t <= tc; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			snackCount = Integer.parseInt(st.nextToken());
			weightLimit = Integer.parseInt(st.nextToken());

			snackWeightArray = new int[snackCount];
			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < snackCount; i++) {
				snackWeightArray[i] = Integer.parseInt(st.nextToken());
			}

			
			getSnackCount(0, 0);
			sb.append("#" + t +" " + result + "\n");
			result =-1;			
		}
		System.out.print(sb.toString());
	}

	static void getSnackCount(int cnt, int start) {			
		if (cnt == 2) {
			int temp = num[0] + num[1];
			if (temp <= weightLimit) {
				result = (temp) > result ? (temp) : result;
			}
			return;
		}

		for (int i = start; i < snackCount; i++) {
			num[cnt] = snackWeightArray[i];
			getSnackCount(cnt + 1, i + 1);			
		}
	}

}