[BAEKJOON] 2798.블랙잭

0. 들어가기에 앞서: 브루트 포스란?

 본 문제는 브루트 포스(brute force)라는 분류에 속해있다.

 브루트 포스는 무차별 대입, 키 전수조사 등으로 불리며 조합 가능한 모든 문자열을 하나씩 대입함으로써 암호를 해독하는 방법을 의미한다.

 학창 시절에 사물함에 비밀번호 기능이 있는 자물쇠를 사용했던 경험이 있다면, 브루트 포스가 어떤 의미인지 대략적으로 이해할 수 있을 것이다.

 3~4자리의 숫자 암호를 해독하는 경우는 자원이 클 필요는 없으나 8자리 등으로 늘어난다면, 해당 암호를 해독하는 데 필요한 자원의 규모는 기하급수적으로 늘어난다. 따라서 브루트 포스를 적용하는 경우, 맨 땅에 헤딩하는 것이 아니라 특정 규칙을 찾아서 대입에 우선순위를 두는 작업이 선행되어야 한다고 생각한다.

 

1. 문제

1.1.문제

  각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력할 것.

 

1.2. 입력

 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

 

1.3. 출력

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

 

1.4. 예제 입출력

1.4.1. 입력

10 500
93 181 245 214 315 36 185 138 216 295

 

1.4.2. 출력

497

 

2. 풀이

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) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] strs1;
		String[] strs2;
		int a = 0;
		int b = 0;
		int c = 0;
		int N = 0;
		int M = 0;
		int sum1 = 0;
		int sum2 = 0;
		
		
		
		try {
        	// 카드의 갯수 N과 숫자 M을 입력받고 
            // split 메소드로 이를 쪼개어 int형으로 변환
			strs1 = br.readLine().split(" ");
			N = Integer.parseInt(strs1[0]);
			M = Integer.parseInt(strs1[1]);
            
            // 입력받은 카드의 갯수 N을 토대로 
            // 해당 카드들에 쓰여 있는 숫자들을 입력받고 쪼갬
			strs2 = new String[N];
			strs2 = br.readLine().split(" ");
			
            // 기본적으로 3장의 카드의 합을 구하는 것이기 때문에
            // a, b, c 카드는 서로 겹치지 않을 것이고
            // a를 가정할 때는 이후 b,c를 가정할 것이기 때문에(i=0) 
           	// 처음부터 전체 갯수에서 2개를 뺀 경우의 수(length-2)가 필요하고
            // b를 가정할 때에는 이미 가정한 a를 제외하고(j=i+1) 
            // 이후 c를 가정할 것이기 때문에
            // 전체 갯수에서 1개를 뺀 경우의 수(length-1)가 필요
			// c를 가정할 때에는 a,b를 가정한 경우를 제외하고(k=j+1) 
            // 이후 나머지 경우를 모두 살펴야하기에 나머지 전체를 봐야함
            for(int i = 0 ; i < strs2.length-2; i++) {
				a = Integer.parseInt(strs2[i]);
				for(int j = i + 1 ; j < strs2.length-1; j++) {
					b = Integer.parseInt(strs2[j]);
					for(int k = j + 1 ; k < strs2.length; k++) {
						c = Integer.parseInt(strs2[k]);
                        //합이 M을 넘지 않도록 처리해주고
						if(a+b+c < M | a+b+c == M) {
							sum1 = a+b+c;
                        // 합을 비교할 수 있는 변수 sum2를 상정하고
                        // 합이 더 큰 경우 sum2에 대입하도록 한 뒤
							sum2 = sum1 > sum2 ? sum1 : sum2; 
						}
					}
				}
			}
			// sum2를 출력하면 결과가 나옴. 
            // 단, BufferedWriter의 write 메소드는 기본적으로 문자형을 매개 변수로 받음.
            // 따라서 개행문자를 추가하여 출력하도록 했음.
            // 만약 변수 sum2만 넣으면 sum2의 숫자값에 해당하는 아스키 코드가 출력됨
			bw.write(sum2+"\n");
			
		} catch (IOException e) {
			e.printStackTrace();
		} finally {
			try {
				bw.flush();
				bw.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}

	}
}