[JAVA] 백준 2798번 블랙잭 : 브루트포스

2798번: 블랙잭

 

1. 문제 추상화

 

주어진 값들 중 세 개를 추출하여 블랙잭 수보다 같거나 작은 최대값을 구하시오.

 

2. 알고리즘

 

굉장히 쉬운 문제지만 브루트포스를 몰라 어렵게 풀었다;;

 

브루트포스(BruteForce)란, Brute( 무식한 )과 Force ( 힘 )의 합성어로 무식한 힘이라는 의미다. 다시 말해서, 무식하게 모든 경우의 수를 탐색하여 조건에 맞는 결과를 내놓는 알고리즘이 효율적일 때가 있다는 말이다.

 

나는 모든 경우의 수를 조사하지 않으려고 오름차순 정렬도 해보고 ArrayList 자료구조도 사용해보았다.  그러나 주어진 조건을 만족하는 규칙을 찾기 어려웠다. 그래서 모든 경우의 수를 조사하는 브루트포스 방식을 찾아보았고 선회하였다.

 

▷ 알고리즘 : 삼중 for문을 만들어 조건에 부합하는 결과를 출력한다.

 

 

3. 코드

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz;
		
		stz = new StringTokenizer(br.readLine());
		
		int num = Integer.parseInt(stz.nextToken());
		int blackjack = Integer.parseInt(stz.nextToken());
        
		int[] arr = new int[num]; // 배열 생성
		
        	// 배열 초기화
		stz = new StringTokenizer(br.readLine());
		for(int i=0; i<num;i++) {
			arr[i] = Integer.parseInt(stz.nextToken());
		}
		
       		// 세 개의 수 찾기
		System.out.println(searchCards(arr,num,blackjack));

	}
	
	public static int searchCards(int[] arr, int num, int blackjack) {
		
		int max = 0;
		int sum = 0;
        
        	// 삼중 for문
		for(int i=0; i<num; i++) {
			sum = arr[i];
			if(sum >= blackjack) continue; // 수 하나로 blackjack수보다 크면 제외
			
			for(int j=i+1; j<num;j++) {
				sum = arr[i] + arr[j];
				if(sum >= blackjack) continue;// 수 두 개로 blackjack수보다 크면 제외
				
				for(int z=j+1; z<num;z++) {
					sum = arr[i] + arr[j] + arr[z]; 
					if(blackjack == sum ) { // 블랙잭수와 같으면 바로 리턴
						return sum;
					}
					
					else if(blackjack > sum && sum > max) { // 블랙잭수와 다르면 최대값 찾기
						max = sum;
					}
				}
			}
		}
		
		return max;
	}

}