[백준] 2798번 : 블랙잭 _ JAVA ( 주석 설명 )

브루트 포스(brute force)

: '완전탐색 알고리즘', 가능한 모든 경우의 수를 모두 탐색하는 방법이다.

BFS(너비 우선 탐색)은 브루트 포스와 관련이 깊고, DFS(깊이 우선 탐색)은 백트래킹과 관련이 깊다.

 

1번

→ 주어진 카드로 만들 수 있는 조합을 전부 탐색하면서 min 값 찾는 문제

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

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

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

        int N = Integer.parseInt(st.nextToken()); //카드의 개수를 입력받는다.
        int M = Integer.parseInt(st.nextToken()); //카드의 합을 입력받는다.

        int[] ary = new int[N]; //카드 개수만큼의 배열 공간을 생성한다.

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;++i){
            ary[i] = Integer.parseInt(st.nextToken()); //각 카드 숫자를 배열에 저장한다.
        }

        int sum = 0; //카드의 합 변수
        int min = -1; //카드의 합 최소값
        //3개의 합, 전수조사를 한다.
        for(int i=0;i<N;++i){
            for(int j=i+1;j<N;++j){
                for(int k=j+1;k<N;++k){
                    sum = ary[i] + ary[j] + ary[k];
                    if(sum<=M && sum>min){ //M을 넘지 않으면서, M에 최대한 가까운 카드 3장의 합을 찾는다.
                        min = sum;
                    }
                }
            }
        }

        System.out.println(min); //M에 최대한 가까운 값을 출력한다.
    }
}