[SWEA] 9229. 한빈이와 SPOT MART - Java

조합을 이용하여 푸는 문제이다. 기본 조합 알고리즘을 이용하여 풀면 쉽게 풀 수 있다.

기본 조합 알고리즘

import java.util.Arrays;

public class CombTest {

    static int[] p = {1,2,3,4,5};
    static int N=p.length;
    static int R=3;
    static int[] num;
    static int tot;

    public static void main(String[] args) {
        tot=0;
        num=new int[R];
        comb(0,0);
        System.out.println(tot);

    }

    private static void comb(int cnt, int start) {

        if(cnt == R) {
            tot++;
            System.out.println(Arrays.toString(num));
            return;
        }

        for (int i = start; i < N; i++) {
            num[cnt] = p[i];
            comb(cnt+1, i+1);
        }
    }

}

문제 코드

import java.util.Scanner;

public class swea_D3_9229 {
    static int TC, N, M;
    static int[] snack;
    static int R = 2;
    static int answer;
    static int[] pick;
    public static void main(String[] args) {
        Scanner scann = new Scanner(System.in);

        TC = scann.nextInt();

        for (int t = 1; t <= TC; t++) {
            N = scann.nextInt();
            M = scann.nextInt();

            answer = -1;
            snack = new int[N];
            pick = new int[R];
            for (int i = 0; i < N; i++) {
                snack[i] = scann.nextInt();
            }
            nCr(0, 0);
            System.out.println("#" + t + " " + answer);
        }
    }
    private static void nCr(int cnt, int start) {
        if (cnt == R) {
            int sum = 0;
            for (int i = 0; i < R; i++) {
                sum += pick[i];
            }
            if (sum <= M) {
                answer = Math.max(answer, sum);
            }
            return;
        }
        for (int i = start; i < N; i++) {
            pick[cnt] = snack[i];
            nCr(cnt + 1, i + 1);
        }
    }
}