[JAVA]2798 블랙잭 완전탐색(조합)

 📚 문제  

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

2798번: 블랙잭

 

🔍 아이디어  

1. 재귀적 풀이는 숫자 3개를 고르는 과정이 조합과 같기 때문에 해당 방식을 이용하였습니다.

2. 반복문 풀이는 숫자 3개를 고르는 과정을 3중 포문을 이용해서 arr에서 i, j, k숫자를 뽑는 경우에 대해서 목푯값과 비교하여 문제를 해결할 수 있습니다.

 

📝 풀이 

1. 재귀적

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class blackjack2796 {
    private static int nearM = 0, m, n;
    private static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = Arrays.stream(br.readLine().split(" ")).mapToInt(i -> Integer.parseInt(i)).toArray();

        dfs(0, 0, 0);
        System.out.println(nearM);
    }

    public static void dfs(int depth, int sum, int start) {
        if (depth == 3) {

            if (Math.abs(nearM - m) > Math.abs(m - sum) && sum<=m) {
                nearM = sum;
            }
            return;
        }
        for (int i = start; i < n; i++) {
            dfs(depth + 1, sum + arr[i], i + 1);
        }
    }
}

 

2. 반복문

package com.example.javaprojtectest2.boj.bruteforce;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class blackjack2796_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int nearM = 0;
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();


        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) { //중복된 숫자가 나올 수 없기 때문에 i번째 숫자 이후에 대해서
                for (int k = j + 1; k < n; k++) {
                    int sum = arr[i]+arr[j]+arr[k]; //숫자 3개
                    if (sum <= m && Math.abs(sum - m) < Math.abs(m - nearM)) {
                        nearM = sum;
                    }
                }
            }
        }
        System.out.println(nearM);
    }
}