[백준 알고리즘][자바] 2798번 : 블랙잭 & 브루트 포스(Brute Force)

브루트 포스

알고리즘의 개념 중의 하나로 영어의 뜻은 다음과 같습니다.

Brute : 난폭한 + Force (힘)

이러한 뜻을 내포하고 있는 이유는 브루트 포스의 알고리즘은 정답으로 도출될 수 있는 모든 경우의 수를 탐색하는 알고리즘이기 때문입니다. 개념적으로 브루트 포스는 완벽한 알고리즘입니다. 왜냐하면 무조건 정답을 도출할 수 있기 때문이죠. 하지만 브루트 포스는 복잡도에 치명적인 단점을 가지고 있고 그에 따라 컴퓨터 자원도 문제가 될 수 있습니다.

 

브루트 포스를 이용하여 문제를 해결하기 위해서는 자료구조는 선형화시키는 것과 경우의 수를 빠트리지 않는 것이 중요하다고 할 수 있습니다.

 

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

2798번: 블랙잭

첫째줄에 카드의 개수 N과 카드의 합 M이 주어집니다.

둘째줄에는 N개 카드의 숫자가 주어집니다.

M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력합니다.

 

예제를 살펴보도록 하겠습니다.

 숫자는 5, 6, 7, 8, 9 가 주어졌고 정답으로는 21이 출력되었습니다.

브루트 포스를 이용하여 처음부터 가능한 정답을 도출해보면

1. 5 + 6 + 7 = 18
2. 5 + 6 + 8 = 19
3. 5 + 6 + 9 = 20
4. 6 + 7 + 8 = 21

정답은 숫자 6, 7, 8입니다. 첫 번째 예제에서는 숫자가 딱 떨어지기 때문에 다음 경우의 수를 살펴보지 않아도 되지만

그렇지 않은 경우도 존재합니다. 두번째 예제를 보도록 하겠습니다.

경우에 따라 다르겠지만, 브루트 포스를 이용하여 문제를 해결할 때 자료를 선형화 시키는 것이 왜 중요한 지 알 수 있는 문제입니다. 만약 위의 예제처럼 숫자가 비선형적이라면 끝까지 경우의 수를 살펴봐야 하지만 아래와 같이 선형적이라면

연속된 세개의 숫자 합이 500이 넘게 되면 프로그램을 종료시킬 수 있습니다.

36 93 138 181 185 214 216 245 295 315

예를 들어, 138 + 181 + 185 = 504 이기 때문에 이후의 숫자의 합은 모두 500이 넘을 것입니다.

만약 비선형적이라면 끝까지 경우의 수를 살펴봐야 하겠습니다.

 

하지만 숫자를 정렬시키기 위한 비용도 수반하기 때문에 정렬을 하는 것인 좋은지 모든 경우의 수를 살펴보는 것이 좋은지 판단해야 할 것입니다. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

// 		백준 알고리즘 2798번
//		카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.
//
//		한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.
//
//		김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.
//
//		이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.
//
//		N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String[] NM = br.readLine().split(" ");
		String[] nums_str = br.readLine().split(" ");

		int N = Integer.parseInt(NM[0]); // 카드의 개수
		int M = Integer.parseInt(NM[1]); // 카드의 합 목표

		int[] nums = new int[N]; // 카드의 숫자들

		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(nums_str[i]);
		}

		int answer = search(nums, N, M);

		bw.write(String.valueOf(answer));

		br.close();
		bw.flush();
		bw.close();

	}

	// 탐색
	static int search(int[] nums, int N, int M) {
		int result = 0;

		for (int i = 0; i < N - 2; i++) {
			for (int j = i + 1; j < N - 1; j++) {
				for (int k = j + 1; k < N; k++) {

					int answer = nums[i] + nums[j] + nums[k];

					if (M == answer) {
						return answer;
					}

					if (result < answer && answer < M) {
						result = answer;
					}
				}
			}
		}

		return result;
	}
}