알고리즘 풀이(JAVA) - 백준 알고리즘_2798(브루트포스-블랙잭)

By on September 5, 2019

브루트포스(brute-force)

  • 브루트포스란?
    brute는 “짐승같은, 난폭한”이라는 뜻이고, brute-force는 “난폭한 힘, 폭력”이라는 뜻이다. 암호학 용어로는 brute-force attack 또는 exhaustive key search, 우리말로는 노가다 또는 무차별 대입 공격이라 부른다. 주로 암호학에서도 쓰이는 방법이긴 하지만, 굳이 암호학만의 문제는 아니고 다른 알고리즘 분야에서도 사용되고 있다. 간단하게 말하자면 노가다와 다굴을 논리적이고 과학적으로 하는 방식.

  • 특징
    조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 문제를 푸는 것인데, 얼핏 무식하다고 생각할 수도 있겠지만 성공한다는 가정 하에 항상 정확도 100%를 보장한다는 점에서, 자원만 충분하면 가장 무서운 방법이다. 이론적으로 가능한 모든 경우의 수를 다 검색해 보는 것이라 정확도 100%가 항상 보장되니, 암호학에서는 가장 확실한 방법으로 통용되고 있다. 무엇보다도 암호 확인 작업이라는 것이 손으로 입력한 문자열의 동일 여부를 확인하는 것이기 때문에, 가능한 경우를 하나씩 대입하다 보면 언젠가는 암호를 찾을 수 있게 되는 식이다. 다만 정말로 그냥 무식하게 때려박는 건 아니고, 숫자만 섞어서 대입해보기 한번, 로마자만 섞어서 대입해보기 한번 이런식으로 하다가 안되면 나머지를 순차적으로 하는 식으로 특정 규칙에 따라 우선순위를 두고 하기도 한다.

문제

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

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

풀이

  • 입력된 모든 카드의 3장을 더한 경우의 수를 찾기 위해 반복문 3번 중첩함.
  • 카드 3장의 값이 M의 값과 동일하면 종료함.
  • 카드 3장의 값이 M의 값보다 크다면 체크하지 않음.
  • 카드 3장의 값이 M의 값보다 작다면 오차 범위가 가장 작은 수를 tmp에 담아 처리함.

소스

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

public class Backjoon_2798 {
	public static void main(String[] args) {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		try {
			String[] inputStr = reader.readLine().split(" ");
			String[] card = reader.readLine().split(" ");
			//카드의 개수
			int N = Integer.parseInt(inputStr[0]);
			//블랙잭 요구 수
			int M = Integer.parseInt(inputStr[1]);
			blackJack(card, M, N);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	private static void blackJack(String[] card, int M, int N) {
		int tmp = 0;
		int A = 0;
		int B = 0;
		int C = 0;
		for(int i = 0; i < N - 1; i++) {
			A = Integer.parseInt(card[i]);
			for(int j = i + 1; j < N - 1 ; j++) {
				B = Integer.parseInt(card[j]);
				for(int k = j + 1; k < N; k++) {
					C = Integer.parseInt(card[k]);
					int sum = A + B + C;
					if(sum == M) {
						System.out.println(sum);
						return;
					}else if(M > sum) {
						if(M - tmp >= M - sum) {
							tmp = sum;
						}
					}
				}
			}
		}
		System.out.println(tmp);
	}
}

Back to blog