백준 2798_블랙잭 [C++]

문제

 

 

풀이

 이 문제는 본인이 뽑은 카드의 합이 21이 넘지 않는 선에서 카드의 합을 최대한 크게 만드는 블랙잭에서 가져온 문제로, 카드의 수 n과 임의의 수 m을 입력받은 다음, n개 만큼의 숫자를 입력받아 주어진 숫자 중 3개를 조합하여 m이 넘지않는 최대값이 얼마인지를 출력하는 문제입니다. 즉 카드 3장으로 만들 수 있는 모든 경우의 수를 비교한 후 최대값을 찾아야 하므로, 조합 가능한 경우를 모두 대입해보는 브루트포스(brute force) 를 이용하면 해결할 수 있습니다.

 조금 더 자세히 설명하면 입력받은 n개의 수 중에서 card[0] + card[1] + card[2] -> card[0] + card[1] + card[3] -> card[0] + card[1] + card[4] ...... 이런식으로 3개의 가능한 조합을 모두 수행해본 후 최대값을 출력해주면 됩니다. 코드는 아래와 같습니다.

 

 

소스코드

#include<iostream>
using namespace std;


int main(){
    int n,m,max=0;
    cin >> n >> m;
    int card[n]={0,};
    for (int i = 0; i < n; i++)
    {
        cin >> card[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++)
            {
                if(card[i]+card[j]+card[k]>max && card[i]+card[j]+card[k]<=m) max= card[i]+card[j]+card[k];
            }
            
        }
    } cout << max;
}