[SWEA-9229][DFS] 한빈이와 Spot Mart - Java

한빈이라는 친구가 과자 두 봉지를 사서 가는데 들고 갈 수 있는 최대 무게를 구하는 문제입니다.

N개 중에서 반드시 두 개를 선택해야 하므로 조합(Combination)을 이용해서 풀면 됩니다.

 

import java.util.Arrays;
import java.util.Scanner;

public class Solution {
    static int[] snacks;
    static int[] selected;
    static int answer;
    static int M;
    private static void dfs(int cnt, int s) {
        if(cnt == 2) {
            int sum = Arrays.stream(selected).sum();
            if(sum > M) return;
            answer = answer > sum ? answer : sum;
            return;
        }

        for(int i = s; i < snacks.length; i++) {
            selected[cnt] = snacks[i];
            dfs(cnt+1, i+1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for(int test_case = 1; test_case <= T; test_case++) {
            int N = sc.nextInt();
            M = sc.nextInt();
            snacks = new int[N];
            selected = new int[2];
            answer = -1;
            for(int i = 0; i< N; i++) 
                snacks[i] = sc.nextInt();
            dfs(0, 0);

            System.out.println("#" + test_case + " " + answer);
        }
    }
}

dfs를 이용해서 조합을 만들어서 선택한 개수가 2개가 되면 합을 구해서 answer과 비교해서 업데이트 해줍니다.

이때, 무게가 초과해서 두 개를 고를 수 없는 경우에 -1을 출력해야 하기 때문에, answer를 -1로 초기화 해주면 아아주 간단합니다.

 

 

매일매일 순열과 조합을 연습하니 이제 쫌 익숙해져 갑니다. 뭐든 꾸준하면 늡니다... 화이팅

 

 

감사함니다 ^_^