[알고리즘] 백준 2798번 "블랙잭" (C/C++) - Don 임베디드

문제요약:

 

일반적인 블랙잭의 규칙은 선택한 카드의 합이 21을 넘지 않는 한도 내에서,

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

오늘은 특별한 블랙잭을 해보려고 한다.

각 카드에는 양의 정수가 쓰여 있다.

딜러는 N장의 카드를 모두 숫자가 보이도록 놓는다.

딜러는 숫자 M을 크게 외친다.

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

플레이어가 고른 카드의 합은 M을 넘지 않으면서 M에 최대한 가까워야 한다.

이 게임에서 항상 이길 수 있도록 프로그램을 만들어보자.

 

 

제약:

 

시간 제한 1초, 메모리 128MB,

3 <= N <= 100, 10 <= M <= 300000,

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

 

 

입력:

 

첫째 줄에는 카드 개수 N과 숫자 M이 공백을 사이에 두고 주어진다.

둘째 줄에는 N개의 카드 숫자가 주어진다.

 

 

출력:

 

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

 

예제 1 입력.	예제 1 출력.
5 21 5 6 7 8 9	21
예제 2 입력.	예제 2 출력.
10 500 93 181 245 214 315 36 185 138 216 295	497

 

 

정답코드:

 

#include <iostream>
 
#define MAX_CARD_NUM    (100)
 
using namespace std;
 
int main()
{
    int N, M;
    int anCardNum[MAX_CARD_NUM];
    int nTmpSum;
    int nResult = 0;
 
    // input N and M value.
    cin >> N >> M;
 
    // input N Cards.
    for (int i = 0; i < N; i++)
    {
        cin >> anCardNum[i];
    }
 
    // Brute Force. Compare all possible options.
    for (int i = 0; i < N - 2; i++)
    {
        for (int j = 1; j < N - 1; j++)
        {
            // Cannot select same card twice.
            if (i == j) { continue; }
 
            for (int k = 2; k < N; k++)
            {
                // Cannot select same card twice.
                if ((i == k) || (j == k)) { continue; }
 
                nTmpSum = (anCardNum[i] + anCardNum[j] + anCardNum[k]);
 
                if (nTmpSum < M)    
                {
                    // if a sum is smaller than M, compare it with current sum.
                    if (nTmpSum > nResult)
                    {
                        // update result as current sum.
                        nResult = nTmpSum;
                    }
                }
                else if (nTmpSum == M)        
                {
                    // if a sum of three cards is M, no need to go further.
                    nResult = nTmpSum;
                    break;
                }
            }
        }
    }
 
    // output the answer.
    cout << nResult << '\n';
 
    return 0;
}

 

원본 링크: https://www.acmicpc.net/