[백준] 2798.블랙잭(Java8)

문제

풀이

package solved2;

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 st = new StringTokenizer(br.readLine()," ");
		
		int n = Integer.parseInt(st.nextToken());//카드의 개수
		int m = Integer.parseInt(st.nextToken());
		int sum = 0;//카드 3장의 합
		int temp;
		int[] arr = new int[n];//카드에 쓰여 있는 수
		st = new StringTokenizer(br.readLine()," ");
		
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		//첫 번째 카드
		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++) {
					temp = arr[i] + arr[j] + arr[k];
					
					if(m == temp) {
						//카드의 합이 m과 같은 경우
						System.out.println(temp);
						return;
					}
					
					if(sum < temp && temp < m) {
						//카드의 합이 이전의 합보다 크고, m보다 작은 경우
						sum = temp;
					}
				}
			}
		}
		
		System.out.println(sum);
		
		br.close();
	}

}

팁

1. 부르트포스(brute force) 알고리즘

• 해당 문제는 부르트 포스 알고리즘을 활용하여 풀 수 있다.
• brute: 무식한, force: 힘   무식한 힘으로 해석할 수 있다.
• 완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.
  - 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구이다.

2. 전체 카드인 N개에서 3개를 고를 수 있는 모든 경우의 수를 탐색하여 합을 구한 뒤, 주어진 M보다 작거나 같은 최댓값을 찾으면 된다.

=> 3중 for문을 활용한다.

//첫 번째 카드                                           
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++) {            
			temp = arr[i] + arr[j] + arr[k];        
			                                        
			if(m == temp) {                         
				//카드의 합이 m과 같은 경우                   
				System.out.println(temp);           
				return;                             
			}                                       
			                                        
			if(sum < temp && temp < m) {            
				//카드의 합이 이전의 합보다 크고, m보다 작은 경우      
				sum = temp;                         
			}                                       
		}                                           
	}                                               
}

출처

2798번: 블랙잭