[백준,BOJ 2798] 블랙잭(JAVA 구현)

 

-내 생각

  완전 탐색(브루트 포스) 알고리즘 분류에 있는 문제이다. 브루트 포스 알고리즘은 모든 경우의 수를 탐색하는 알고리즘이므로 문제에서 3장의 카드를 뽑는다 했으므로, 3장의 카드에 들어올 수 있는 모든 경우의 수를 따져보고자 했다. 이때, 3장의 카드는 5, 6, 7이나 6, 5, 7 이나 어차피 최종적으로 모두 합친 값으로 m과 비교해야하기 때문에 탐색을 위한 반복문 3개 중 두 번째와 세 번째 반복문은 항상 앞의 반복문보다 +1 된 상태로 시작하게 한다. 또한 끝나는 부분은 세 장은 세 자리의 숫자를 의미하므로 첫 번째 반복문은 2번째, 3번째 자리의 숫자만큼 공간이 있어야 하므로 끝까지 비교하지 않고 끝에서 -2 한 인덱스 까지만 비교하게 하며 2번째 반복문 역시 마찬가지다.

 

  문제에 대한 해법은 문제를 읽어보고 알아낼 수 있었는데, 어째서인지 계속 오답처리가 나서 의아했는데 m에 가까운 최댓값을 저장하는 변수인 max값을 첫 번째 반복문 안에서 계속 초기화를 해버려서 그랬던 것이었다.... 코드를 보면 이해가 쉬울 것이다.

 

-해법

 

import java.util.*;



public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt(); //n 입력
		int m = sc.nextInt(); //m 입력
		
		int arr[]=new int[n]; // n만큼의 정수카드 입력배열
		
		
		for(int i=0;i<arr.length;i++) {
			arr[i] = sc.nextInt();
		}
		
		int temp =0; // 3장의 카드값이 저장 될 변수
		int max=0;	 // 3장의 카드값이 저장되는 수 중 m과 가장 가까운 maax값 변수
		for(int i=0;i<arr.length-2;i++) {	// 첫 번째부터 뒤에 두자리를 남길때까지 반복	
			// m=Integer.MIN_VALUES; // 이 자리에 잘못된 코드가 들어갔었다..
            for(int j=i+1;j<arr.length-1;j++) { // 두 번째부터 뒤에 한자리를 남길때까지 반복
				for(int k=j+1;k<arr.length;k++) { // 마지막 자리수이므로 끝까지 반복
					temp = arr[i]+arr[j]+arr[k]; // 각 자리의 정수의 합
										
					if(temp<=m&&temp>max) {	//max값을 찾는 과정에서 m보다 작거나 같은 조건을 추가해
                     						//m에 가까운 최대값을 찾을 수 있다.
						max = temp;	//m에 가까운 최대값이 저장				
					}											
				}
			}
		}
		
		System.out.println(max); // 출력
		
		
	}
	
}