[백준] 2798번 블랙잭 | Miran Lee 👩‍💻

DFS, Brute Force

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

풀이

쉬운 문제 찾다가 브론즈 2인 블랙잭 문제를 선택했다. 레벨이 낮은 걸 아니까 복잡하게 생각할 필요없이 그냥 삼중 포문 돌려서 풀었다. 말그대로 Brute-Force의 정석..ㅎ 정렬시켜서 Flag를 사용해 나름 조건부 탈출을 시키려고했으나 어짜피 N의 최댓값은 100이니까 그냥 모든 경우의 수를 다 따졌다! 블랙잭F&Q 이 게시글을 보면 이 문제의 의도가 잘 담겨져 있다.

그리고 경우의 수 문제니까 DFS로도 풀어봤다. 기저 사례(base case, 재귀함수 실행 중에 더 이상 쪼갤 수 없는 조건)가 DFS에서 얼마나 중요한지 깨달았다. pos>=N인 경우를 기저사례에 포함시키지 않으니까 코드가 안돌아갔다. 꼼꼼히 문제를 확인해서 놓치는 조건이 없는지 잘 확인해야겠다. 문제가 약간 로또 + 퇴사 짬뽕이다. 지금까지 DFS 문제를 풀면서 느끼는 건 형식은 항상 같다는 것!

void DFS(int index, int sum){
    if(조건)
    출력 or 대입
    return;
    if(기저사례)
    return;
    

    DFS(index+1, sum+index); //건너 뛰지 않을 때
    DFS(index+1, sum); //건너 뛸 때
}

약간 이런 느낌??

코드

사용언어: C++

DFS

#include <iostream>
#include <stdio.h>
using namespace std;

#define MAX 100

int card[MAX];
int close = 0;
int N, M;

void DFS(int pos, int cnt, int sum)
{
    if (cnt == 3)
    {
        if (sum <= M)
        {
            close = max(sum, close);
            return;
        }
    }
    if (sum > M || cnt > 3 || pos >= N) //base case
        return;

    //카드를 선택한 경우
    DFS(pos + 1, cnt + 1, sum + card[pos]);
    //카드를 선택하지 않은 경우
    DFS(pos + 1, cnt, sum);
}

int main()
{
    scanf("%d %d", &N, &M);

    for (int i = 0; i < N; i++)
    {
        scanf("%d", &card[i]);
    }

    DFS(0, 0, 0);
    cout << close << endl;
}

BRUTE-FORCE

#include <iostream>
#include <stdio.h>
using namespace std;

#define MAX 100

int card[MAX];

int solution(int N, int M)
{
    int sum = 0;
    int close = 0; //제일 가까운 수 저장
    bool flag = false;
    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++)
            {
                sum = card[i] + card[j] + card[k];

                if (sum == M)
                {
                    return M;
                }
                if (close < sum && sum <= M)
                {
                    close = sum;
                }
                // if (sum > M)
                //     break;
            }
        }
    }

    return close;
}

int main()
{
    int N, M;
    scanf("%d %d", &N, &M);

    for (int i = 0; i < N; i++)
    {
        scanf("%d", &card[i]);
    }

    cout << solution(N, M) << endl;
}

출처

백준