블랙잭

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	128124	62052	47699	47.297%

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다.

카드의 합이 21을 넘지 않는 한도 내에서,

카드의 합을 최대한 크게 만드는 게임이다.

블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은

새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다.

그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다.

그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다.

블랙잭 변형 게임이기 때문에,

플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때,

M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다.

둘째 줄에는 카드에 쓰여 있는 수가 주어지며,

이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

예제 입력 1

5 21
5 6 7 8 9

예제 출력 1

21

예제 입력 2

10 500
93 181 245 214 315 36 185 138 216 295

예제 출력 2

497

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #6 1번

• 문제를 번역한 사람: baekjoon
• 빠진 조건을 찾은 사람: bupjae
• 문제의 오타를 찾은 사람: eric00513, joonas, otter66

알고리즘 분류

• 브루트포스 알고리즘

---

문제를 보자마자 ‘브루트 포스로’ 모든 경우의 수를 확인해야 한다고 생각했다.

그 이유는 카드를 뽑는 데 규칙이 없었기 때문인 것 같다.

카드의 개수가 N개로 주어지고 3장을 뽑아서 ( 중복 X )

그 3장의 합이 M과 같거나 작은 값을 찾는 문제로 규칙이 없기 때문에 브르투 포스 알고리즘을 사용하면

N * N-1 * N-2 만큼의 시간이 걸릴 것으로 예상.

코드를 3중 for문으로 나올 수 있는 모든 경우의 수를 확인하면서 M값보다 작거나 같은지

또는 전에 저장한 결과 값 보다 큰 수인지 확인하여 문제를 해결하였다.

카드의 수의 범위가 100이하이고 뽑는 카드의 수가 3개라서

3중 for문을 사용해도 시간 초과가 나지 않는다. (제한 시간 1초)

i, j, k가 서로 겹치는 예외도 따로 처리해 주었다.

통과된 코드

#include <iostream>

using namespace std;

int N, M;

int arr[100];

int temp, sum = INT32_MIN;

int main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	for (int  i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i == j) { continue; }
			for (int k = 0; k < N; k++) {
				if (i == j || j == k || i == k) { continue; }
				temp = 0;
				temp = arr[i] + arr[j] + arr[k];
				if (sum < temp && M >= temp) {
					sum = temp;
				}
			}
		}
	}

	cout << sum;

	return 0;
}

3중 for 문의 범위를 잘못 작성하여 틀렸다.

추가적으로 반복문을 돌릴 때 나는 모든 범위에서 예외를 제거하는 방식으로 작성했지만

https://artiper.tistory.com/79

이런 방식으로 돌리는 게 더 좋은 코드인 것 같다.