[백준 c++] 2798 블랙잭 (블2)

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

 

📌 문제

블랙잭 규칙인 카드의 합이 21을 넘지 않는 한도 내에 카드의 합을 최대한 크게 만드는 게임이다.

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

 

해당 문제는 완전탐색으로 모든 경우의 수를 다 찾으면 된다.

문제의 특이점은 꼭 3장을 골라야한다는 점이다.

그래서 중첩 루프문을 3개 겹쳐서 3개를 고른 모든 경우의 수를 탐색하면 된다.

 

 

참고로 재귀함수를 사용한 완전탐색일 경우 시간초과로 인해 문제를 풀지 못한다.

알고리즘 문제 풀이는 대부분 시간 싸움이기 때문에 재귀함수는 그래서 되도록이면 사용하지 않는 것이 좋다.

재귀함수는 말 그대로 함수를 꼬리가 꼬리를 물면서 함수 호출이 이뤄지기 때문에

코드가 비교적 간단해도 속도가 느려질 수도 있다는 점을 조심해야한다. 

 

 

 

💻 정답 코드

#include <iostream>

using namespace std;

int main() {

	int N; cin >> N; if (N < 3 || N > 100) return 0;
	int M; cin >> M; if (M < 10 || M > 300000) return 0;

	int* num = new int[N];
	for (int i = 0; i < N; i++) cin >> num[i];
	//숫자 입력칸

	int min = 9999999999;
	int result;

	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 = num[i] + num[j] + num[k];
				int dis = M - sum;
				if (dis >= 0 && dis < min) {
					min = dis;
					result = sum;
                    if(result == M){
                        cout <<result << endl;
                        return 0;
                    }
				}

			}
		}
	}

	cout << result << endl;

	return 0;
}

 

⏱ 결과