[Java] BOJ 2798 블랙잭

문제 

문제 링크 https://www.acmicpc.net/problem/2798

• N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.
• 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다.
• 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.
• 합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.
• 첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

아이디어

• 카드 세장의 합을 구했을 때, 배열에 저장하는데, 그 합이 겹칠 수도 있으니 중복 숫자가 들어가지 않는 set을 활용해야겠다고 생각했다.
• 카드 세장의 조합은 재귀로 구하면 되겠다고 생각을 하였다. 

겪은 시행착오

• 일단... 재귀가 너무 오랜만이라... 방법이 생각이 안나서 많이 헤맸던 것 같다. 이번 기회에 제대로 다시 숙지를 해야겠다...
• 그리고 또 오래걸린 이유가 있다.. 문제를 또 제대로 안읽고 풀었다...분명 세장의 합이 M보다 작아야된다고 문제에 적혀있는데... 그걸 무시하고 Math.abs(M - 세장의 카드 합) 이런식으로 풀었었다...쉬운문제지만 정말 오래걸린 문제였다...ㅠㅠ
• 그리고 이제 보니까 굳이 배열에 저장안하고 재귀 돌려서 카드 3개의 합을 구할때마다 최솟값이랑 비교해서 갱신했으면 속도가 더 빨랐을텐데...라는 생각이 든다.. 다음부터는 참고해서 문제를 풀어야겠다...

'맞았습니다'를 위한 험난한 여정... (그냥 3중 for문으로 풀껄 그랬나...)

솔직히 틀린게 3번 넘어가면서부터 짜증이 나기 시작했다... 분발하자...ㅜㅜ

코드

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class BOJ2798 {

    // 카드 합이 중복될 수 있으므로 중복값이 들어가지 않는 set을 사용
    static Set<Integer> cards_sum = new HashSet<>();
    static int cards_num[];
    static int N;
    static int arr[] = new int[3];

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 카드의 개수
        N = Integer.parseInt(st.nextToken());
        // 만들어야되는 최대한 가까운 수
        int M = Integer.parseInt(st.nextToken());
        // 결과값
        int result = 0;

        // 카드 숫자 저장할 배열
        cards_num = new int[N];

        StringTokenizer st2 = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++){
            int c = Integer.parseInt(st2.nextToken());

            // 카드 번호 저장
            cards_num[i] = c;
        }

        cards(0, 0);

        // 차이 최솟값을 찾기 위한 변수
        int min = Integer.MAX_VALUE;

        // set에는 순서가 없으므로 다시 배열로 전환
        int sumArr[] = new int[cards_sum.size()];

        int idx = 0;

        // 배열로 전환
        for(int i : cards_sum){
            sumArr[idx] = i;
            idx = idx + 1;
        }

        // 조합하여 합을 구한 카드 값 배열에서 가장 근접한 값 찾기 위해 반복
        for(int i = 0; i < sumArr.length; i++){
            // M을 넘지 않아야 하므로
            if(M >= sumArr[i]){
                if(min > (M - sumArr[i])){
                    result = sumArr[i];

                    min = M - sumArr[i];
                }
            }
        }

        System.out.println(result);
    }

    public static void cards(int n, int m){
        // 카드 세개가 조합이 됐을 경우,
        if(n == 3){
            // 해당 카드 3개의 숫자를 더함
            cards_sum.add(arr[0] + arr[1] + arr[2]);
        }
        else{
            // 중복된 값이 들어가지 않기 위해 i = m
            for(int i = m; i < N; i++){
                // 카드 3개를 조합하는 배열에 카드 한개를 넣음
                arr[n] = cards_num[i];
                // 한개가 들어갔으므로 깊이 + 1
                n = n + 1;
                // 선택한 다음카드부터 조합에 사용하기 위해서 + 1
                // 다음 카드 조합하러감
                cards(n, i + 1);
                // 다른 카드도 조합하기 위해서 깊이 초기화
                n = n - 1;
            }
        }
    }
}