부르트포스 - 백준 블랙잭 2798

부르트 포스는 가능한 모든 경우의 수를 실행해보는 것이다. 복잡하지만 의외로 간단하기도 한 문제이다. 

https://www.acmicpc.net/problem/2798

2798번: 블랙잭

백준 단계별 풀기 중 브루트 포스 중 가장 낮은 정답률의 블랙잭 문제에 대해 풀이 해보겠다. N장의 카드를 뿌린 다음 3장을 고른다. 고른 3장이 M보다 크지 않으면서 최대한 가깝게 만들면된다. 

 

이 문제는 단순하게 모든 경우를 진행해보면 된다. 예를들어서 index로 생각하면 

 

0 1 2

0 1 3

0 1 4

...

....

...

 

이런식으로 모든 경우를 진행한 후 M보다 작거나 같은지 확인하고 이전에 값 중 가장 큰 값인지 확인하면 된다. 이 문제 상에서는 3장을 뽑는다고 결정되어있기 때문에 3중 반복문을 활용하여 간단하게 풀 수 있었다. 

 

#include <stdio.h>

int card[1020];

int main(){
	int N, M; // N 카드 수 M 카드 크기 제한
	
	int count=0, max = 0;

	scanf("%d %d", &N, &M);

	for(int i = 0; i < N; i++)
		scanf("%d", &card[i]);
	
	for(int i = 0; i < N; i++)
		for(int j = i+1; j< N; j++)
			for (int k = j+1; k<N;k++){
				if(card[i] + card[j] + card[k] <= M && card[i] + card[j] + card[k] > max){
					max = card[i] + card[j] + card[k];
				}
			}

	printf("%d", max);
}