[baekjoon] 2798 : 블랙잭 (C++)

문제

---

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

 

예제 입출력

---

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

2798번: 블랙잭

 

문제 풀이

---

이 문제를 보고 설마 for문 여러개를 중첩시켜 푸는 문제인가 싶었다. 아닐거라 믿고 다른 방법을 고민해봤는데 별다른 방법이 생각나지 않아 결국 for문 3개를 중첩시켜 문제를 푸는 방식을 선택했다. 머릿속으로 생각했을땐 복잡할거라 생각했었는데 생각보다 간단했고 살짝 생각을 했었던 부분은 for문안에 for문을 넣을때 변수 시작값이었다.

첫 for문에서의 변수 i는 0부터 N번까지, 두번째 for문부터는 변수 j의 시작은 i + 1부터 N까지, 세번째 for문의 변수 k는 j + 1부터 N까지로 만들어 주었다. 이렇게 해야 같은 케이스를 반복해서 계산하지 않기 때문이다. 처음 0번째, 1번째, 2번째를 더했었는데 모든 for문을 0부터 시작하면 앞과 똑같은 2번째 0번째 1번째도 더할 경우가 있어 이것을 방지해주기 위해서였다.

 

최종 코드

---

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int N, M, c;
	int blackjack, answer = 0;
	cin >> N >> M;
	vector<int> card;
	for (int i = 0; i < N; i++) {
		cin >> c;
		card.push_back(c);
	}
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			for (int k = j + 1; k < N; k++) {
				blackjack = card[i] + card[j] + card[k];
				if (blackjack <= M && answer < blackjack)
					answer = blackjack;
			}
		}
	}
	cout << answer;
}