[BaekJoon 2798][🟤2] 블랙잭

❓ 문제

백준 2798 - “블랙잭”

🎯 난이도

Bronze 🟤2

🧠 풀이

1. 내 풀이 (브루트 포스)

- 알고리즘

• Brute Force

- 설명

• 시간 제한 1초
• 메모리 제한 128MB
• 3 <= N <= 100

이라는 조건 하에서는, 브루트 포스 알고리즘으로 충분하다고 생각해서 삼중 반복문으로 간단히 해결했다.

사실상 코드로만 따지만 완전히 간략하게 삼중 반복문으로만 할 수 있지만, 개인적으로 조금이라도 더 최적화를 하고 싶어서 가지치기용 코드를 많이 추가했다.

삼중 반복문의 완전 탐색 방식이므로 O(N³)의 시간 복잡도를 가진다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>

#include <algorithm>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{}, iM{};
    cin >> iN >> iM;

    vector<int> vecCard(iN, 0);
    for(int i = 0; i < iN; ++i)
    {
        cin >> vecCard[i];
    }

    sort(vecCard.begin(), vecCard.end());

    int iMax{ 0 };

    for(int i = 0; i < iN - 2; ++i)
    {
        int iSum1{ vecCard[i] };

        // 현재 시점 최솟값이 iM보다 크면 바로 break;
        if(iSum1 + vecCard[i + 1] + vecCard[i + 2] > iM)
        {
            break;
        }
        // 현재 시점 최대값이 iMax보다 작거나 같으면 건너 뜀
        else if(iSum1 + vecCard[iN - 1] + vecCard[iN - 2] <= iMax)
        {
            continue;
        }

        for(int j = i + 1; j < iN - 1; ++j)
        {
            int iSum2{ iSum1 + vecCard[j] };

            // 지금 값이 iM보다 크거나 같으면 바로 break;
            if(iSum2 >= iM)
            {
                break;
            }
            // 현재 시점 최대값이 iMax보다 작거나 같으면 건너 뜀
            else if(iSum2 + vecCard[iN - 1] <= iMax)
            {
                continue;
            }

            for(int k = j + 1; k < iN; ++k)
            {
                int iSum3{ iSum2 + vecCard[k] };

                // 원하는 값 찾으면 바로 출력 후 종료
                if(iSum3 == iM)
                {
                    cout << iM;
                    return 0;
                }
                // 최종값이 iM보다 크면 break;
                else if(iSum3 > iM)
                {
                    break;
                }

                // 조건 만족시 iMax 값 갱신
                iMax = iMax < iSum3 ? iSum3 : iMax;
            }
        }
    }

    cout << iMax;

    return 0;
}

---

2. 추가 풀이 (투 포인터)

- 알고리즘

• Two Pointer

- 설명

내 풀이가 아마 문제에서 의도한 정석에 가깝다고는 생각하지만, 그래도 이 풀이가 더 좋아 보여서 가져왔다.

투 포인터 알고리즘을 사용해서 반복문을 세 번 중첩에서 두 번 중첩으로 줄일 수 있다. 속도 상으로 꽤나 큰 이득이기 때문에, 쓰면 안될 이유가 없다. 물론 투 포인터를 쓰기 위해 정렬을 해야하지만, 이는 sort를 사용하면 부담 없이 해결할 수 있다.

투 포인터 알고리즘으로 반복문 중첩을 한 번 줄여서 시간 복잡도가 O(N²)이다.

- 코드

추가 풀이 코드

#include <iostream>

#include <vector>

#include <algorithm>


using namespace std;

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{}, iM{};
    cin >> N >> M;

    vector<int> vecCard(iN);

    for(int& iCard : vecCard)
    {
        cin >> iCard
    }

    // 투 포인터를 사용하려면 정렬 필수
    sort(vecCard.begin(), vecCard.end());

    int iMax{};
    for (int i = 0; i < iN - 2; ++i) 
    {
        int iLeft{ i + 1}, iRight{ N - 1 };

        while (iLeft < iRight) 
        {
            int iSum = vecCard[i] + vecCard[iLeft] + vecCard[iRight];

            if (iSum == iM) 
            { 
                cout << iM; 
                return 0; 
            }
            // 합이 iM보다 작으면 iMax 갱신하고 ++iLeft로 범위 축소
            if (iSum < iM) 
            { 
                iMax = max(iMax, iSum); 
                ++iLeft; 
            }
            // 합이 iM 보다 작을 경우 --iRight로 범위 축소
            else 
            { 
                --iRight; 
            }
        }
    }

    cout << iMax;
}

---

💭 후기

나는 브루트 포스를 쓰고 최적화를 위해 많은 가지치기용 코드를 추가했지만, 투 포인터만으로도 간단히 더 빠른 알고리즘으로 해결할 수 있다는 것을 알았다.

간단히 풀려도 좀 더 나은 풀이 방법은 없을지 고민해보는 시간을 가지는게 좋을 것 같다.

🔗 참고자료

• 브루트 포스 알고리즘
• 투 포인터 알고리즘