[백준][C++][브루트포스] 2798번 블랙잭

문제

문제 링크 - 블랙잭

풀이

알고리즘

• N개의 카드 오름차순 정렬
• 카드 배열에서 가장 큰 것부터 3개 카드의 index를 뽑음
• 3개 숫자의 index를 순열을 이용하여 중복되지 않는 경우의 순열 탐색
• 나온 순열의 합 중 M보다 작거나 같은 경우만 내림차순 정렬된 우선순위 큐에 넣어줌
• 우선순위 큐의 가장 윗부분 원소를 출력

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

void BlackJack(int N, int M, vector<int> card)
{
    priority_queue<int, vector<int>, less<int>> answer_q;
    sort(card.begin(), card.end());

    int big_idx = card.size() - 1;
    int mid_idx = card.size() - 2;
    int sml_idx = card.size() - 3;

    int sum_temp;

    while (big_idx > 1)
    {
        sum_temp = card[sml_idx] + card[mid_idx] + card[big_idx];

        if (sum_temp <= M)
            answer_q.push(sum_temp);

        if (sml_idx > 0)
        {
            sml_idx--;
        }
        else if (mid_idx > 1)
        {
            mid_idx--;
            sml_idx = mid_idx - 1;
        }
        else
        {
            big_idx--;
            mid_idx = big_idx - 1;
            sml_idx = mid_idx - 1;
        }
    }

    cout << answer_q.top() << endl;
}

int main()
{
    int N, M;

    cin >> N >> M;
    vector<int> card(N);

    for (int i = 0; i < card.size(); i++)
    {
        cin >> card[i];
    }

    BlackJack(N, M, card);
}

주석 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

void BlackJack(int N, int M, vector<int> card)
{
    //카드들을 오름차순 정렬
    sort(card.begin(), card.end());

    //내림차순 정렬된 우선순위 큐 선언
    priority_queue<int, vector<int>, less<int>> answer_q;

    //가장 큰 3개 카드의 index
    int big_idx = card.size() - 1;
    int mid_idx = card.size() - 2;
    int sml_idx = card.size() - 3;

    int sum_temp;

    //3장의 카드의 합을 구해야하므로
    //sml_idx=0, mid_idx=1, big_idx=2 일 때까지 반복
    while (big_idx > 1)
    {
        //카드 3장의 합
        sum_temp = card[sml_idx] + card[mid_idx] + card[big_idx];

        //과정 출력
        cout << "idx: [" << sml_idx << " " << mid_idx << " " << big_idx << "] ,  ";
        cout << card[sml_idx] << " + " << card[mid_idx] << " + " << card[big_idx] << " = ";
        cout << sum_temp << endl;

        //카드 3장의 합이 M보다 작으면 answer_q에 넣어줌
        if (sum_temp <= M)
            answer_q.push(sum_temp);

        //sml_idx ==> card.size()-3 ~ 0
        if (sml_idx > 0)
        {
            sml_idx--;
        }
        //mid_idx ==> card.size()-2 ~ 1
        else if (mid_idx > 1)
        {
            mid_idx--;
            sml_idx = mid_idx - 1;
        }
        //big_idx ==> card.size()-1 ~ 2
        else
        {
            big_idx--;
            mid_idx = big_idx - 1;
            sml_idx = mid_idx - 1;
        }
    }

    //정답 출력
    cout << "answer: " << answer_q.top() << endl;
}

int main()
{
    int N, M;

    cin >> N >> M;
    vector<int> card(N);

    for (int i = 0; i < card.size(); i++)
    {
        cin >> card[i];
    }

    BlackJack(N, M, card);
}

주석 코드 출력 결과

[입력]
N=5, M=21
5 6 7 8 9

[출력]
idx: [2 3 4] ,  7 + 8 + 9 = 24
idx: [1 3 4] ,  6 + 8 + 9 = 23
idx: [0 3 4] ,  5 + 8 + 9 = 22
idx: [1 2 4] ,  6 + 7 + 9 = 22
idx: [0 2 4] ,  5 + 7 + 9 = 21
idx: [0 1 4] ,  5 + 6 + 9 = 20
idx: [1 2 3] ,  6 + 7 + 8 = 21
idx: [0 2 3] ,  5 + 7 + 8 = 20
idx: [0 1 3] ,  5 + 6 + 8 = 19
idx: [0 1 2] ,  5 + 6 + 7 = 18
answer: 21

여담

나는 보통 인상깊게 푼 문제만 겨우겨우 포스팅하는데, 사실 이 문제를 풀고 포스팅을 할 생각은 없었다. 그런데 다른 분들의 풀이를 보던 와중에 3중 for문을 통하여 풀이한 코드만 있는 것을 확인하고 내 풀이도 도움이 될까 싶어 올려본다.

3중 for문이 아닌 while문 하나로 풀었다는 점만 빼면 효율성 측면에서는 크게 차이는 없을 것 같다. 하지만 3중 for문보다는 좀 더 직관적이지 않나 싶긴하다. 아님 말고.

우선순위 큐를 사용해준 이유는 속도를 좀 더 높일려는 이유 말고는 없다. vector를 이용해서 sort해도 풀이 자체에는 문제가 없다.

왜 순열을 뒤에서부터 찾았느냐하면 처음에 왠지 뒤에서부터 하고싶어서 그렇게 했다. 앞에서부터 찾아도 똑같다.