[SWEA] 9229 한빈이 Spot Mart (D3, 조합) - Java

링크

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

SW Expert Academy

 

 

 

문제 해석

과자를 두 봉지 사야 함
무게 제한을 벗어나면 살 수 없음
무게합 최대를 찾아라

- 각 테스트케이스 별 입력
첫 번째 줄 : N M # 과자 개수, 최대 무게
두 번째 줄 : N개의 무게 정보

 

 

 

코드

import java.io.*;
import java.util.*;

public class Solution {
	static int maxWeight;
	static int M;

	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 test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken()); // 과자 개수
			M = Integer.parseInt(st.nextToken()); // 최대 무게

			int[] arr = new int[N]; // 과자 무게 정보 저장

			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < arr.length; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}

			maxWeight = 0;
			recursive(arr, new int[2], 0, 0);
			if (maxWeight == 0) {
				maxWeight = -1;
			}
			System.out.println("#" + test_case + " " + maxWeight);

		} // [E] test_case
	}

	private static void recursive(int[] arr, int[] sel, int aIdx, int sIdx) {
		// basis part
		if (sel.length == sIdx) {
//			System.out.println(sel[0] + " " + sel[1]);
			if (sel[0] + sel[1] > maxWeight && sel[0] + sel[1] <= M) {
				maxWeight = sel[0] + sel[1];
			}
			return;
		}

		// inductive part
		for (int i = aIdx; i < arr.length; i++) {
			sel[sIdx] = arr[i];
			recursive(arr, sel, i + 1, sIdx + 1);
		}
	}
}

 

 

 

코드 해석

순서 상관 없음
중복 불가
-> 조합 문제

 

단순 조합 문제입니다.

 

가중치 등의 문제가 발생하지 않으므로 조합으로 선택 배열만 잘 도출한다면 쉽게 푸실 수 있습니다.

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice