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

 

 

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

2798번: 블랙잭

 

---

[1] 문제

 

 

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 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

 

 

 

 

---

[2] 정답 및 해설

 

 

 

# 정답 코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void) {

	int N, M;
	int a[100];
	int max = 0, sum = 0;


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

	for (int i = 0; i < N; i++) {
		scanf("%d", &a[i]);
	}

	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++) {
				sum = a[i] + a[j] + a[k];
				if ((sum > max) && (sum <= M)) {
					max = sum;
				}
			}
		}
	}

	printf("%d", max);

	return 0;

}

 

 

# 해석

 

for문이 세 번 중첩된 반복문에 대해 설명하겠다.

이 부분에서는 배열 a에서 가능한 모든 세 숫자 조합을 확인하고, 그 중에서 합이 M 이하인 가장 큰 값을 찾는다.

문제의 핵심 알고리즘이다.

 

 

for (int i = 0; i < N - 2; i++): 첫 번째 반복문은 i를 0부터 N - 2까지 증가시킨다. 이는 배열의 첫 번째 원소부터 뒤에서 두 번째 원소까지를 기준으로 선택하는 역할을 한다.

 

for (int j = i + 1; j < N - 1; j++): 두 번째 반복문은 j를 i + 1부터 N - 1까지 증가시킨다. 이는 기준이 되는 i번째 원소 다음부터 마지막에서 두 번째 원소까지를 선택하는 역할을 한다.

 

for (int k = j + 1; k < N; k++): 세 번째 반복문은 k를 j + 1부터 N까지 증가시킨다. 이는 기준이 되는 j번째 원소 다음부터 마지막 원소까지를 선택하는 역할을 한다.

 

 

이제, 이 세 개의 반복문이 동작하면서 i, j, k는 서로 다른 배열의 인덱스를 가리키게 된다. (내가 떠올리지 못한 부분)

이 인덱스들을 사용하여 배열 a에서 세 개의 숫자를 선택하고(a[i], a[j], a[k]), 이들의 합을 계산하여 sum에 저장한다.

 

그런 다음, if문을 사용하여 sum이 현재까지의 최대값 max보다 크고, 동시에 M 이하인지 확인한다.

만약 그렇다면, max를 sum으로 업데이트한다.

이렇게 하면 현재까지 확인한 조합 중에서 가장 큰 합이 max에 저장된다.

 

 

마지막으로, 모든 반복문이 실행된 후에는 max에 저장된 값이 가장 큰 합이므로 이를 출력한다.

 

이렇게 해서 프로그램은 배열 a에서 가능한 모든 세 숫자 조합 중에서 합이 M 이하인 가장 큰 값을 찾고 출력한다.

 

 

 

 

---

[3] 느낀 점

 

 

 

배열과 for문을 이용해서 입력받은 숫자 크기만큼 scanf를 이용하는 건 전에 풀었던 문제 덕분에 알고 있었다.

 

 

배열 a에서 가능한 모든 세 숫자 조합을 확인하는 알고리즘에 대한 아이디어가 도무지 떠오르지 않았다.

 

브루트포스 알고리즘을 이용한다고 한다.

 

그런데 그게 뭔지 몰라서 전혀 도움이 되지 않았다...

 

구글링을 통해 문제를 풀었는데

 

정답 코드를 확인하니 반복문을 세 번 사용하면서 모든 경우의 수를 만들어내는 아이디어를 떠올리는 게 관건인 것 같았다.

 

사용하는 문법은 배운 내용인데 실제로 사용해서 문제를 풀어내는 과정이 어려운 것 같다,..

 

 

 

---

[4] 추가 학습

 

 

 

https://hawaiian-pizza-it.tistory.com/39

[알고리즘 기본] 완전 탐색 (브루트 포스 Brute Force)

 

 

브루트포스 알고리즘은 ... 거창한 이름만큼 엄청난 알고리즘은 아니고

 

 

Brute Force 직역하면 짐승같은 힘, 무식한 힘이라는 뜻이다.
완전 탐색이라는 이름에서도 알 수 있듯이 하나부터 열까지 모든 경우를 다 탐색하는 알고리즘이다.
 
모든 경우를 탐색하니 당연히 정답을 찾을 수 있다.

 

라고 한다.

주로 반복문을 중첩하여 사용할 수 있다고 한다.

그리고 암호해독 기법으로도 많이 사용된다고 한다.