백준 2798번 블랙잭 [C언어] - 브루트 포스

브루트 포스는 완전 탐색으로

문제를 해결하기 위해 가능한 모든 경우의 수를 계산하는 방법이다.

전체 탐색을 하기 때문에 정답을 찾는 데에선 문제가 없다.

하지만 탐색 시간이 오래걸리는 단점이 있다.

 

데이터셋의 구조에 따라

1. 선형구조 : 순차탐색

2. 비선형구조 : BFS, DFS

로 문제를 해결한다.

/*
	브루트 포스
*/
#include <stdio.h>
#pragma warning(disable: 4996)
int card[100] = { 0, };
int main() {
	int m, n;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n;i++)
		scanf("%d",&card[i]);
	int min = m;
	int index[3] = { 0, }; // 카드 인덱스
	for (int i = 0; i <n; i++) {
		for (int j = 0; j < n;j++) {
			if (j == i)
				continue; // 중복 방지
			for (int k = 0; k < n;k++) {
				if (k == i || k == j)
					continue; // 중복 방지
				int sum = 0;
				sum = card[i] + card[j] + card[k];
				if (sum <= m) { //합이 m값을 넘지 않게
					if (min > m - sum)
					{
						index[0] = i;
						index[1] = j;
						index[2] = k;
						min = (m - sum);
						if (min == 0) //조건 달성
							break;
					}
					
				}
			}
		}
	}
	printf("%d", card[index[0]] + card[index[1]] + card[index[2]]);
}