[SW9299] 한빈이와 Spot Mart

 

 SW Expert Academy - 한빈이와 Spot Mart 

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW8Wj7cqbY0DFAXN&categoryId=AW8Wj7cqbY0DFAXN&categoryType=CODE&problemTitle=%ED%95%9C%EB%B9%88&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&& 

SW Expert Academy

 

문제 입출력

4
3 45
20 20 20
6 10
1 2 5 8 9 11
4 100
80 80 60 60
4 20
10 5 10 16	// 테스트 케이스 개수
// 첫 번째 테스트 케이스 N = 3, M = 45
// 3개의 과자 봉지 무게 a1 = 20, a2 = 20, a3 = 20

#1 40
#2 10
#3 -1
#4 20	//첫 번째 테스트 케이스 결과
//두 번째 테스트 케이스 결과
//세 번째 테스트 케이스 결과
//네 번째 테스트 케이스 결과

 

문제 풀이

package day220808.problem;


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


public class HW_한빈이와SpotMart {
	static int T, N, M;
	static int[] snack;
	static int max;
	static StringBuilder sb = new StringBuilder();


	// 조합 메서드
	private static void comb(int cnt, int start, int sum) {
		// 만약 과자의 무게가 M 보다 크다면 return
		if (sum > M) return;

		// 집은 과자의 갯수가 2개라면 기저 조건
		if (cnt == 2) {
			max = Math.max(max, sum); // 최댓값을 갱신
			return;
		}

		// 자기 자신 다음부터 봐도 된다.
		for (int i = start + 1; i < N; i++) {
			sum += snack[i];

			comb(cnt + 1, i, sum);
			sum -= snack[i]; // 빠져나오면 더한 값을 다시 빼준다.
		}

	}


	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			// 변수 입력
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());

			// 배열 입력
			snack = new int[N];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				snack[i] = Integer.parseInt(st.nextToken());
			}

			// 만약 최댓값이 없다면 -1 로 갱신되도록 초기값 설정
			max = -1;
			comb(0, -1, 0); // 0 인덱스에 해당하는 값도 세야하므로 -1 부터 시작

			sb.append("#" + t + " ").append(max + "\n");

		} // end tc

		System.out.println(sb.toString()); // 답 출력

	} // end main
}

 

 

 

 

 

 

 

 

 

 

# SW Expert Academy 한빈이와 Spot Mart

---