[SWEA] 9229. 한빈이와 Spot Mart - java

문제설명은 간략하게 하겠습니다.
주어진 과자들에서 두 봉지를 집어 m무게 이하로 과자를 가져가면 되고 집어갈 수 있는 범위내에 가장 큰 값을 구하면 됩니다.

 

n: 과자수 , m: 들고갈수있는 최대무게

n=6  m=10 
1 2 5 8 9 11

 

이렇게 되어있으면 1, 9 이렇게 집어 정답은 10이 됩니다.

 

이 문제를 풀기위해 크게 투포인터, DFS로 풀 수 있는데 저는 DFS를 선택했습니다.

그런데 최대한 재귀를 덜 시키기위해 조합이 되도록 DFS를 구성했습니다 예를 들어

1 2 5 8 9 11

이 과자봉지들이 있으면  (1,2) 를 집으면 재귀로 다시 (2,1)을 집지 않는거죠. 1,2에서 집었기 때문입니다.

조합을 이용해 최소한으로 재귀한 다음 문제를 해결했습니다. 자세한 방법은 아래 전체코드에 dfs부분 주석참고

전체코드

import java.util.*;

class Solution
{
    static int [] arr;
    static int [] pm,ch ;
    static int m;
    static int answer;
    
    public void dfs(int l,int s){
    	// 두봉지만 집기때문에 2에서 멈춤
    	if(l==2){
            if(pm[0]+pm[1] <= m) answer= Math.max(answer, pm[0]+pm[1]);
        }
        else{
            //조합
            for(int i=s;i<arr.length;i++){
                pm[l]=arr[i];
                dfs(l+1,i+1);
            }
        }
    }
	public static void main(String args[]) throws Exception
	{

		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		for(int tc = 1; tc <= T; tc++)
		{	
                    answer=-1;
                    int n = sc.nextInt();
                    m = sc.nextInt();
                    arr = new int[n];
                    ch = new int[n];
                    pm = new int[2];
                    for(int i=0;i<n;i++) arr[i]= sc.nextInt();
                    Solution s = new Solution();
                    s.dfs(0,0);
                    System.out.println("#"+tc+" "+answer);
		}
	}
}