[백준/Java]Q2798

백준 알고리즘 11단계 브루트 포스 2798번 문제입니다.

---

Q. 블랙잭 게임
각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.
이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.
N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

[입력]

- 첫째 줄에 카드의 개수 N과 M이 주어진다.

- 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

 

[조건]

- 3 ≤ N ≤ 100

- 10 ≤ M ≤ 300,000

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

 

풀이

11단계는 브루트 포스 알고리즘으로 분류된다.

브루트 포스(Brute force)는 모든 경우의 수를 검색하는 완전 탐색 알고리즘이다. 가능한 모든 경우의 수를 계산하기 때문에 100% 정확도를 가지지만 실행 시간이 오래 걸린다는 단점이 있다. 아마 그런 측면에서 이름이 지어진 것이 아닐까 싶다.(Brute : 무시한, force : 힘)

 

돌아와서,

이 문제는 입력받은 수 N만큼의 수를 나열하고, N만큼의 수들 중 세 수의 합이 M에 가장 근접한 합을 구하는 문제였다.

 

예제를 만들어 시뮬레이션을 돌려봤다.

N : 5, M : 21 인 경우 3, 9, 5, 8, 12 다섯가지 수를 입력받고 세 수를 차례로 더해보면 20이 가장 근접한 합이 된다.

1. 3 9 5  : 17
2. 3 9 8  : 20
3. 3 9 12 : 24
4. 3 5 8  : 16
5. 3 5 12 : 20
6. 3 8 12 : 23
7. 9 5 8  : 22
8. 9 5 12 : 26
9. 9 8 12 : 29
10. 5 8 12 : 25

이 예제를 프로그래밍해보면 다섯가지 수를 배열에 담고(인덱스 0부터) 각 배열의 인덱스를 증가시키며 계산하는 그림이 그려진다.

1. [0] + [1] + [2] - 0번째 인덱스부터 검색, for(int i = 0; i < n - 2; i++)
2. [0] + [1] + [3]
3. [0] + [1] + [4]
4. [0] + [2] + [3]
5. [0] + [2] + [4]
6. [0] + [3] + [4]
7. [1] + [2] + [3] - 1번째 인덱스부터 검색, for(int j = i + 1; j < n - 1; j++)
8. [1] + [2] + [4]
9. [1] + [3] + [4]
10. [2] + [3] + [4] - 2번째 인덱스부터 검색, for(int h = j + 1; h < n; h++)

이 때, 0, 1번째 인덱스는 n - 2, n - 1까지만 반복하도록 하는데 이유는 총 세 수의 합을 구해야하기 때문이다.

3중 for문 구조에서 0번째 인덱스를 N까지 제한하면 0, 1, 2, 3, 4 까지 루프를 돌기 때문에 순차적으로 세 수의 합을 구할 수 없다.

 

합을 구한 후에는 temp(최초 0으로 설정, 이후 합을 temp에 담는다) 보다 크면서 m보다 작은 수를 담게한다.

이 과정을 반복하게 되면 최종적으로 m에 가장 근접한 합이 남게 된다.

 

소스

package com.baek.algo.step11;

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

public class Q2798 {

	public static void main(String[] args) throws IOException {		
		BufferedReader bf   = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st  = new StringTokenizer(bf.readLine(), " ");
		StringTokenizer st2 = new StringTokenizer(bf.readLine(), " ");

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[] card = new int[n];
		int min = 0;
		int sum = 0;
		int result = 0;

		for(int i = 0; i < n; i ++) {
			card[i] = Integer.parseInt(st2.nextToken());
		}

		for(int i = 0; i < n - 2; i++) {
			for(int j = i + 1; j < n - 1; j++) {
				for(int h = j + 1; h < n; h++) {				
					sum = card[i] + card[j] + card[h];
                    
					if(sum <= m && sum >= min) {
						min = sum;
						result = sum;
					}
				}
			}
		}

		System.out.println(result);

		bf.close();
	}
}