[SWEA] 9229번 한빈이와 Spot Mart

링크

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

풀이

n개 중에 반드시 2개를 뽑아서 제한무게를 넘지않는 최대 무게를 구하는 문제다. 순서 상관없이 특정 개수를 뽑는 문제이므로 조합 완전탐색을 이용해서 풀었다.
조합의 경우, 순열과 달리 방문 여부 조건이 필요없고 시작 인덱스가 재귀 프레임마다 바뀌기 때문에 다음 재귀 매개변수로 i+1 를 넘겨준다.

🍀 시작인덱스가 있어야
1. 한 경우의 수에서 원소가 중복되지 않는다.
2. 전체 경우의 수에서도 중복되는 조합이 발생하지 않는다.

visit배열은 arr배열 인덱스를 값으로 한다.
🌵 재귀를 돌아온 후에는 cnt값을 원상복귀 해줘야한다.

코드

import java.util.*;
import java.io.*;
/**
 * spot mart
 * 완전탐색
 * n개 중에 2개를 뽑아서 제한무게를 넘지않는 최대 무게를 출력.
 * @author dnflr
 *
 */
public class Solution_9229_이광용 {
	static int ans, n, m;
	static int [] arr, visit;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		
		for(int t = 1; t <= tc; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			n  = Integer.parseInt(st.nextToken());
			m  = Integer.parseInt(st.nextToken());
			ans = -1;
			
			st = new StringTokenizer(br.readLine());
			arr = new int[n];
			visit = new int[2]; //arr배열 인덱스를 값으로 함.
			for(int i = 0; i <  n; i++) {
				arr[i] = Integer.parseInt(st.nextToken()); 
			}
			dfs(0, 0);
			System.out.println("#" + t + " " + ans);
		}
	}
	public static void dfs(int cnt, int sIdx) {
		if(cnt == 2) {
			int tmpSum = 0;
			for(int j = 0; j < 2; j++) {
				tmpSum += arr[visit[j]];
			}
			if(tmpSum <= m) {
				ans = Math.max(ans, tmpSum);
			}
			return;
		}
		else {
			for(int i = sIdx; i < n; i ++ ) {
				visit[cnt] = i;
				cnt++;
				dfs(cnt, i + 1);
				cnt--;
				
			}
		}
	}
}