JAVA 백준 문제풀이 (15) 2798: 블랙잭

 

해당 문제는 브루트포스 카테고리에 속해있다.

브루트 포스란 무엇인가? 

 

암호학에서, 무차별 대입 공격(영어: brute-force attack)은 특정한 암호를 풀기 위해 가능한 모든 값을 대입하는 것을 의미한다. 대부분의 암호화 방식은 이론적으로 무차별 대입 공격에 대해 안전하지 못하며, 충분한 시간이 존재한다면 암호화된 정보를 해독할 수 있다. 하지만 대부분의 경우 모든 계산을 마치려면 실용적이지 못한 비용이나 시간을 소요하게 되어, 공격을 방지하게 한다. 암호의 '취약점'이라는 의미에는 무차별 대입 공격보다 더 빠른 공격 방법이 존재한다는 것을 의미한다.

 

이것은 암호학의 얘기이지만 알고리즘도 별 다를 거 없다.

원하는 값이 도출될 때까지 모든 경우의 수를 대입하는 것을 브루트포스라고 한다.

 

 

브루트는 이런 뜻인데.. 아마 브루트포스를 한국말로 하자면 그냥 "무식한 노가다"정도 될 것 같다.

브루트 포스는 연산이 복잡할수록 성능이 극악으로 떨어지기 때문에 효율은 좋지 않지만, 역설적이게도 원하는 값을 찾을 수 있는 가장 정확한 방법이다..

 

사설이 길었다. 브루트포스를 이용해서 해당 문제를 풀려면 어떻게 해야할까?

뽑아야할 카드가 세장이니 삼중 for문 세개 달아주고 모든 카드 조합을 죄다 계산해보면 된다.

 

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        // 제공되는 카드 수
        int cardDraw = Integer.parseInt(st.nextToken());
        // 최대값
        int baseValue = Integer.parseInt(st.nextToken());

        ArrayList<Integer> cardArr = new ArrayList<>();
        // 최대 합을 저장할 변수
        int max = 0;

        // 카드 목록
        st = new StringTokenizer(br.readLine(), " ");

        while (st.hasMoreTokens()) {
            cardArr.add(Integer.parseInt(st.nextToken()));
        }

        // 같은 카드끼리 반복해서 연산할 필요가 없기 때문에 i,i+1,i+2로 반복문을 돌린다
        for (int i=0; i<cardArr.size()-2; i++) {
            for (int j=i+1; j<cardArr.size()-1; j++) {
                for (int k=j+1; k<cardArr.size(); k++) {
                    int sum = cardArr.get(i) + cardArr.get(j) + cardArr.get(k);
                    if ( sum <= baseValue ) {
                        if ( max < sum ) {
                            max = sum;
                        }
                    }
                }
            }
        }
        System.out.println(max);
    }
}