#2789번 블랙잭 (c++)

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int card_num = 0;
    int ans = 0;
    cin >> card_num >> ans;
    int arr[card_num];
    int total = 0;
    
    for(int i=0; i<card_num; i++)
        cin >> arr[i];

    for(int i=0; i<card_num-2; i++)
    {
        for(int j=i+1; j<card_num-1; j++)
        {
            for(int x=j+1; x<card_num; x++)
            {
                if(arr[i]+arr[j]+arr[x]<=ans)
                {
                    if(arr[i]+arr[j]+arr[x]>=total)
                        total = arr[i]+arr[j]+arr[x];
                }
            }
        }
    }
    cout << total;
    return 0;
}

이 문제의 카테고리가 'Bructe force'라는 점에 주의해야한다. 

굳이 기교를 부리고 어떻게 하면 효율성을 높일지는 따질 필요가 없다. 

정말 무식하게 풀고 간단하게 생각하면 되는 문제다.

 

처음에 2~3번정도 오류가 났는데, Brute force라는 주제를 벗어나 새로운 방식으로 접근하다보니 틀리게 되었다. 

혹 테스트 케이스는 통과했는데 틀린 경우가 있다면, 아래 백준의 블랙잭 FAQ를 참고하면 도움이 될것이다.

 

https://www.acmicpc.net/board/view/47357

글 읽기 - ★☆★☆★ [필독] 블랙잭 FAQ ★☆★☆★

1. 이 문제는 모든 경우의 수를 정직하게 따져보는 것이 의도인 문제입니다. 수행 시간을 줄이기 위한 묘기는 따로 필요하지 않습니다. 물론 실제로 시간 복잡도를 개선하는 것이 불가능한 것은 아니나, 문제의 제한인 N <= 100은 모든 가능한 세 카드의 조합을 1초 내에 뽑아보는 데에 전혀 무리가 없는 제한이기 때문에 전부 해보아도 되고, 반면에 증명할 수 없는 방법으로 탐색을 중도에 종료하도록 하는 것은 매우 위험합니다.
2. 예를 들어, 굳이 카드를 정렬할 필요가 없습니다. 어차피 모든 경우의 수를 따져볼 것이기 때문입니다.
3. 루프 중간에 break를 할 필요도 없습니다. 그것 때문에 따져보지 못하는 경우가 생깁니다.
4. 세 카드를 뽑는 로직을 다르게 할 필요도 없습니다. 예를 들어, 첫 두 장을 먼저 연속된 카드로 뽑아놓고 나머지 한 장을 루프를 돌려 찾는 방식으로 하면 틀립니다. 첫 두 장이 연속되지 않게 하는 것이 최적일 수도 있습니다. 세 장을 모두 같은 방법으로 뽑으세요.
5. 답 갱신은 세 장을 뽑았을 때마다 하면 됩니다. 굳이 분기를 나눠서 어떨 땐 갱신을 미루고, 다른 변수에 저장해보는 등 할 필요가 없습니다. "M을 넘지 않으면서 지금까지 찾았던 최댓값보다 크다면, 답을 갱신한다"를 모든 경우에 대해 똑같이 수행하면 됩니다.

나는 위의 붉은 글씨들을 무시했다가 2~3번 정도 틀리게 되었다.

'이렇게 무식하게 푸는게 정말 좋은 알고리즘일까? 더 세련되고 간결하고, 효율성 높게 짜는 방법을 따져야 하지 않나...'

라는 생각이 들었지만, 위에 붉은 문장들을 곰곰히 읽다보면 Brute force가 갖는 이점이 알 수 있다.