[백준] 2798 블랙잭

https://www.acmicpc.net/problem/2798

2798번: 블랙잭

 

이 문제말고도 다른 문제에서 꽤 많이 나오는 것 같아서 순열과 조합에 대한 개념을 확실히 익혀놔야 할 것 같다.

카드의 개수가 최대 100으로 고정되어 있기 때문에 모든 경우의 수를 구한 뒤 하나씩 비교해도 시간초과가 뜨지 않았다.

 

---

문제 및 입출력

 

---

코드

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

public class Main
{
    // 배열의 값 중 3개를 골라더하는 모든 경우의 수 만들기
    public static void makeNum(int sum, int cnt, int len, int[] arr, boolean[] flag, ArrayList<Integer> list)
    {
        if(cnt==len)
        {
            list.add(sum);
            return;
        }
        
        for(int i=0; i<arr.length; i++)
        {
            if(!flag[i])
            {
                flag[i] = true;
                makeNum(sum+arr[i], cnt+1, 3, arr, flag, list);
                flag[i] = false;
            }
        }
    }
    public static void main(String[] args)
    {
        // 기본 입력값 설정
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        
        for(int i=0; i<n; i++)
        {
            arr[i] = sc.nextInt();
        }
        
        // 입력으로 받은 배열의 합 경우의 수를 구하기 위한 설정
        ArrayList<Integer> list = new ArrayList<Integer>();
        boolean[] flag = new boolean[n];
        Arrays.fill(flag, false);
        makeNum(0, 0, 3, arr, flag, list);
        
        // 목표값보다 작은 값들 중에서 가장 큰 값을 출력
        int result = Integer.MIN_VALUE;
        
        for(int d : list)
        {
            if(d<=m)
            {
                result = Math.max(result, d);
            }
        }
        
        System.out.println(result);
    }
}