백준 2798번 _ BlackJack 블랙잭 / Brute Force 브루트포스 (C++)

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

2798번: 블랙잭

필자는 호주워홀시절 카지노에서 블랙잭으로 꽤나 큰 돈을 잃어본 적이 있다... 또르륵..
여튼 오늘도 각설하고, 또 백준이 블랙잭을 이용한 재미있는 게임을 만든 모양이다.
게임은 단순하다.
처음에 카드의 갯수와 타겟 넘버를 입력하고
카드의 갯수만큼 숫자가 주어지면, 카드 중 세개를 골라 더한 값이 가장 타겟넘버와 가까워지는 값을 구하는 것이다.

이건 브루트 포스 문제다. 브루트 포스는(Brute force) 무차별 대입이란 뜻을 가졌는데, 한 마디로 무식하게 모든 경우의 수를 생각하는 것이다.
그렇다면 이 문제는 가능한 숫자 세개의 조합을 모두 구해서 더한 값 중 타겟넘버와 가장 가까운 값을 찾으면 끝이다.
답안 역시 무식하게 for문 세개를 돌리고자 한다.
Time Complexity는 n^(3) 까지 올라가겠지만, 카드의 갯수가 100개보다 작으니 그리 오래걸리진 않을 것 같다.

코드는 다음과 같다.

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


int main(){
    int num, M; // 카드갯수와 타겟넘버 입력.
    cin>>num>>M;
    int card[num];
    for (int i=0; i<num; i++)
    {
        cin>>card[i]; // 카드 넘버 입력.
    }
    int answer = card[0] + card[1] + card[2];

    for (int i=0; i<num; i++)
    {
        for (int j=i+1; j<num; j++)
        {
            for (int k=j+1; k<num; k++)
            {
                if (abs(card[i]+card[j]+card[k]-M) < abs(answer-M) && card[i]+card[j]+card[k] <= M)
                {
                    answer = card[i]+card[j]+card[k]; // 타겟넘버와 더 가까우면 계속 업데이트
                }
            }
        }
    }
    cout<<answer;
    return 0;
}

끝!