[C++] 백준 2798번: 블랙잭

2798번: 블랙잭

이 문제의 제목을 봤을 때, 뭔가 어렵겠구나 라고 느꼈지만 생각보다 어렵지 않다. 풀이는 간단하다. 모든 경우를 싹 조사하면 된다.

경우의 수도 얼마 안 된다. N이 최대 100인 것을 고려했을 때 입력된 카드들 중 3장을 뽑아서 합을 구하는 모든 수는 조합에서 배웠다시피 100 * 99 * 98 = 970,200밖에 되지 않는다. 1GHz의 CPU에서 연산하는데 9ms밖에 걸리지 않는다.

각 합을 담을 배열도 용량이 크지 않다. 970,200 * 4(byte) = 3,880,800 byte ≒ 3.7 MB 밖에 되지 않는다.

그래서 마음놓고 for문을 3번 중첩하여 모든 경우를 계산하고

	int count = 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 = cards[i] + cards[j] + cards[k];
				if (sum <= M) {
					jacks[count] = sum;
					count++;
				}
			}
		}
	}

최대 크기가 970,200 칸 밖에 되지 않는 합을 보관한 배열의 각 값을 확인해서 답을 구할 수 있다.

	int suitable_idx = 0;
	int minimal_diff = M;
	for (int i = 0; i < count; i++) {
		if (M - jacks[i] < minimal_diff) {
			minimal_diff = M - jacks[i];
			suitable_idx = i;
		}
	}
	printf("%d\n", jacks[suitable_idx]);

전체 코드는 아래와 같다.

#include <cstdio>

int main() {
	int N, M;
	scanf("%d %d", &N, &M);
	int* cards = new int[N];
	int* jacks = new int[N * (N - 1) * (N - 2)];
	for (int i = 0; i < N; i++) {
		scanf("%d", cards + i);
	}
	int count = 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 = cards[i] + cards[j] + cards[k];
				if (sum <= M) {
					jacks[count] = sum;
					count++;
				}
			}
		}
	}
	int suitable_idx = 0;
	int minimal_diff = M;
	for (int i = 0; i < count; i++) {
		if (M - jacks[i] < minimal_diff) {
			minimal_diff = M - jacks[i];
			suitable_idx = i;
		}
	}
	printf("%d\n", jacks[suitable_idx]);
	delete[] cards;
	delete[] jacks;
	return 0;
}