백준 2798번 - 블랙 C++

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

2798번: 블랙잭

 

오늘은 과거에 풀었던 경험이 있는 블랙잭 문제를 공유하고자 한다. 아래사진은 문제를 캡처 후 문제를 풀기 위해 중요하다고 생각하는 키워드 및 문장을 따로 하이라이트 하였다. 아래 문구를 보고 우리는 완전 탐색 문제(Brute Force)라는 것을 알아야 한다. 또한, 100,000을 넘지 않는다는 문구를 통해 Data Type은 Int 형이면 되겠다 까지만 파악하면 된다. ※ Brute Force 알고리즘에 관해서는 나중에 따로 포스팅하도록 하겠다.

 

 

 완전 탐색 문제라는 것이 파악이 되었다면, 그 이후 알고리즘은 간단하다. 그 이유는 모든 경우의 수를 다 계산해 보면 되기 때문이다. 다만 여기서 알고리즘을 어려워하는 사람의 경우 저 문구만 보고 어떻게 완전 탐색 문제라는 거야?라는 의문을 가질 수 있다. 간단하게 설명하면 "최대한 가장 가까운 카드"라는 문구에서 "최대한 = 모든 경우의 수를 다 보야아한다"를 의미한다. 우리가 살면서 "최대한 노력해 봐 = 내가 할 수 있는 모든 걸 다 해봐"라는 것과 비슷한 맥락이라고 이해하면 좋을 것 같다. ※ 아래에 구현한 코드를 기재해두었으니, 참고하면 될 것 같다. 

#include <stdio.h>
#include <math.h>
#include <iostream>

using namespace std;
const int MAX_CARD_COUNT = 100;
const int MAX_CARD_NUMBER = 300000;

int g_iCountOfCard = 0;
int g_iCardNumber = 0;
int g_iCardNumList[MAX_CARD_COUNT];

/************************************************
@함수명	: Input
@기능	: 입력받는 함수
@입력값	:
@출력값	:  
@비고	:
*************************************************/
void Input()
{
    cin >> g_iCountOfCard;
    cin >> g_iCardNumber;
    for (int index = 0; index < g_iCountOfCard; ++index)
    {
        cin >> g_iCardNumList[index];
    }
}

/************************************************
@함수명	: FindNearestNum
@기능	: 가장 가까운 총합을 찾는 함수
@입력값	:
@출력값	: 가장 가까운 총합
@비고	:
*************************************************/
int FindNearestNum()
{
    int iNearestNumber = 0; // 정답과 가장 가까운 합
    int iCardNumSum = 0; // 카드 총합
    for (int firstIndex = 0; firstIndex < g_iCountOfCard - 2; ++firstIndex)
    {
        for (int seconIndex = firstIndex + 1; seconIndex < g_iCountOfCard - 1; ++seconIndex)
        {
            for (int thridIndex = seconIndex + 1; thridIndex < g_iCountOfCard; ++thridIndex)
            {
                iCardNumSum = g_iCardNumList[firstIndex] + g_iCardNumList[seconIndex] + g_iCardNumList[thridIndex];

                if (iCardNumSum <= g_iCardNumber)
                {
                    if (iNearestNumber < iCardNumSum)
                    {
                        iNearestNumber = iCardNumSum;
                    }
                }
            }
        }
    }

    return iNearestNumber;
}

/************************************************
@함수명	: main
@기능	: 메인문
@입력값	:
@출력값	: 
@비고	:
*************************************************/
int main()
{
    Input();

    cout << FindNearestNum();
    return 0;
}

 

 

제출 결과