[C++] 백준 2798 블랙잭

www.acmicpc.net/problem/2798

2798번: 블랙잭

 

1. 서론

 

용기 내면 풀 수 있는 문제... 무슨 용기냐면 3중 for문을 쓸 수 있는 용기

 

2. 문제 풀이

 

블랙잭 게임 룰을 조금 뒤튼 문제. 카드의 개수 n과 세 개의 카드를 더했을 때 나와야 하는 값 m이 주어진다.

그리고 n개의 카드값들이 주어진다. 이 카드 값들 중 세 개의 카드를 더해 m보다 작거나 같은 범위 내에서 가장 m에 가까운 수를 구하는 문제이다.

조합 문제라고 생각했는데 복잡하게 재귀로 푸는 건 아닌 것 같고 어떻게 푸는 걸까 고민하다가 완전 탐색으로 푸는 문제라고 해서 반신반의하면서 for문을 3개를 써서 풀었다. (카드를 세 개를 뽑아야 하기 때문에) 3개의 반복문으로 카드를 뽑으면서 더해서 m과 비교해 작거나 같은 값에서 최고의 값을 구하는 max 함수를 썼다. 

 

3. 코드 설명

 

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int m, n, i, j, k, x, t = 0;
    int a[100];
    
    cin >> n >> m;

    for (i = 0; i < n; i++)
        cin >> a[i];
    
    for (i = 0; i < n; i++)
    {
         for (j = i + 1; j < n; j++)
         {
             for (k = j + 1; k < n; k++)
            {
                x = a[i] + a[j] + a[k];
                if (x <= m)
                    t = max(t, x);  
            }
        }
    }
    
    cout << t << endl;
}

 

필요한 값을 입력 받고 for문 세 개를 돌려 카드를 선택한다.

이때 m보다 작거나 같은 수에 한 해 max() 함수를 돌려서 최고의 값을 가려낸다.

 

+ 이거는 사실 풀이를 어디서 본 거고 난 i, j, k를 똑같이 0부터 시작해서 돌렸다가 그냥 조합이 아니라 중복 조합으로 뽑히는 바람에

i, j, k가 같지 않을 때를 조건으로 따로 줬고, max 함수를 쓸 생각을 못하고 벡터에 값을 넣었다가 sort를 돌려서 가장 마지막 값을 뽑았다.

맞긴 했는데 메모리가 엄청 들었다... (벡터에 많은 값이 들어갔고, sort까지 했기 때문에) 한 마디로 머리를 더 굴리기 싫어서 컴퓨터한테 일을 더 많이 시킨 샘이다... ㅎ 다음에 내가 이 범위를 활용할 수 있을까 의문