(C++) 백준 2798번 [블랙잭]

안녕하세요 평범한컴공생입니다.

 

오늘은 백준 2798번 블랙잭 문제 알고리즘 포스팅을 해보겠습니다.

전형적인 브루트포스(완전탐색)문제로 모든 경우의 수를 탐색해주어 문제에서 원하는 값을 구해주면 됩니다.

 

1. 문제 해결 방법 구상하기

 - 먼저 N과 M을 입력받고 N번만큼 반복문을 돌려 카드의 값들을 입력받는다.

 - M에 최대한 가까운 카드? >> 최솟값을 저장하는 변수 min 을 선언하고 각 조합마다 비교하여 더 작을 시 min에 대입하여준다.

 - 3장의 카드이므로 반복문을 3중으로 설계해서 돌리면 모든 조합의 수를 탐색할 수 있다.

 

2. 구상한 아이디어를 바탕으로 코딩하기

#include <iostream>

int main()
{
	using namespace std;

	int N, M;
	cin >> N >> M;

	int card_value[100] = { 0 }; 
	/* N의 값이 최대 100 이므로 100개의 element를 가진 배열을 선언
	그리고 0으로 초기화해준다. */

	for (int n = 0; n < N; n++)
	{
		cin >> card_value[n];
	}

	int i, j, k; // 세 장의 카드의 합의 완전탐색을 위해 3중의 반복문 필요
	int min = M;
	int sum = 0;
	// 최솟값 min 에 1,2,3번째의 카드값의 합과 M과의 차이를 초기화해줍니다.
	// sum 은 1,2,3번째 카드값의 합을 초기화해줍니다.

	for(i=0; i<N-2; i++)
		for(j=i+1;j<N-1;j++)
			for (k = j + 1; k < N; k++)
			{
				if ((M-(card_value[i] + card_value[j] + card_value[k]) <= min)&& (M - (card_value[i] + card_value[j] + card_value[k]))>=0)
				{ // M의 값보다 카드 세장의 합이 넘어가면 안되므로 위와 같은 두 조건이 만족하여야 한다.
					min = M-(card_value[i] + card_value[j] + card_value[k]);
					sum = card_value[i] + card_value[j] + card_value[k];
				}
			}

	cout << sum << endl;

	return 0;
}

처음에 문제를 풀 때 제대로 문제를 읽지 않아서 M보다 카드 세장의 합이 넘어가면 안된다는 조건을 확인하지 못하여 차를 구하는 함수를 설정하고 M보다 카드 세장의 합이 넘어가는 경우도 생각하여 풀어 오답을 제출했었다. 다음부터는 문제 조건을 꼼꼼하게 확인하여 문제 설계를 하도록 하자!

 

 

// 피드백 및 문제사항 제기 언제든지 감사히 받겠습니다.