브루트포스 - 백준 2798번 블랙잭

www.acmicpc.net/problem/2798

2798번: 블랙잭

IDEA

3중 for문을 사용하면 카드의 개수가 100개뿐이기에 최악의 경우에도 1000000 정도밖에 안된다. 

투포인터(??)처럼 생각했다. 

정렬을 한 이후 i, j, k 세 카드의 합이 블랙잭의 한도인 m을 넘어가는 경우 어차피 그 이후를 탐색해봤자 계속 m을 넘을테니 break를 걸어주어 다음 카드 조합으로 넘어가게 해주었다. 

ex ) 1 3 5 7 8

m = 10 i = 1 , j = 3 , k = 7인 경우 합이 10을 넘기때문에 동일한 i,j에 대해 k는 더 이상 움직일 필요 없어 break

만약 m보다 작거나 같은 경우 answer와 비교해 더 큰 값을 answer에 저장해준다. 어느 값이 m을 넘지 않으며 가장 큰 값인지 모르기때문에 가장 큰 숫자가 아닐지더라도 여태까지 나온 수 중에 가장 크다면 answer에 저장해주는거다.

answer는 어차피 커봤자 m을 넘지 못하기때문이다. 

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int arr[100];
	int n , m;
	scanf("%d %d", &n , &m);
	for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
	sort(arr, arr + n);
	int answer = 0;
	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++) {
				int sum = arr[i] + arr[j] + arr[k];
				if (sum > m) break;
				else answer = max(sum, answer);
			}
		}
	}
	printf("%d", answer);
}