[JAVA][SWEA][D3] 9229. 한빈이와 Spot Mart

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

문제의 출처는 아래의 사이트 입니다. 

SW Expert Academy

 

1. 문제에서 요구하는것

재귀를 적절하게 사용하고 가지치기를 할 수 있는가?

 

2. 입력

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

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

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

이후 N개의 줄에 각 과자봉지의 무게 가 주어진다. (1 ≤ ai ≤ 1000000)

 

3. 문제의 내용

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

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

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

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

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

 

4. 정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Solution{
	static List<Integer> list;
	static int answer;
	static int sum = 0;
	static int M = 0;
	static int N;
	static int[] arr; // 과자를 담는 배

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int T = Integer.parseInt(st.nextToken());
		for (int tc = 0; tc < T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken()); // 과자 봉지의 개수
			M = Integer.parseInt(st.nextToken()); // 목표 과자 무게
			st = new StringTokenizer(br.readLine());
			arr = new int[N];
			for (int i = 0; i < N; i++) {
				arr[i] = (Integer.parseInt(st.nextToken()));
			}
			// 조합 재귀 구현.
			sum = 0;
			answer = 0;
			Combination(0, 0);
			System.out.printf("#%d ", tc + 1);
			if (answer == 0) {
				System.out.println(-1);
			} else
				System.out.println(answer);

		}
	}

	static void Combination(int start, int cnt) {
		if (sum > M) {
			return;
		}

		if (cnt == 2) {
			if (sum == M) {
				answer = M;
				return;
			}

			if (sum < M && sum > answer) {
				answer = sum;
				return;
			}
			return;
		}
		for (int i = start; i < N; i++) {
			sum = sum + arr[i];
			Combination(i + 1, cnt + 1);
			sum = sum - arr[i];
		}

	}
}