[백준] 2798번: 블랙잭 | C++ 풀이

# 문제

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

 

 

---

 

# 풀이

solved.ac 클래스 2에 속하고 백준 단계별 풀이로는 브루트 포스에 해당하는 문제!

정답 소스코드를 보며 필요한 개념을 정리해보자.

 

우선 브루트포스 알고리즘이란 완전탐색 알고리즘이다. 즉, 모든 경우의 수를 전수조사하여 정답을 찾아낸다.

어떻게 보면 가장 기본적이고도 핵심적인 방법이지만, 코드 수행시간이나 메모리 측면에서 효율이 떨어진다.

그래도 다른 효율적인 해결 방법을 알아보기 위해서라면 꼭 한번쯤 생각해보고 넘어가야 하는 단계!

바로 정답 소스코드를 확인해보자.

 

#include <iostream>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    int arr[n];
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }

    int card;
    int maxSet = 0;
    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++){
                card = arr[i]+arr[j]+arr[k];
                if(card <= m && maxSet < card) maxSet = card;
            }
        }
    }
    cout << maxSet;
    return 0;
}

앞서 설명한 것처럼 모든 경우를 탐색하면 되기 때문에 3장의 카드 조합을 모두 따져 원하는 결과값을 찾으면 된다.

 

 

 

int n, m;
cin >> n >> m;
int arr[n];
for(int i=0; i<n; i++){
    cin >> arr[i];
}

문제에서 주어진 n과 m을 입력받고, n장의 카드를 입력받을 크기 n의 1차원 배열을 만든다.

for문을 돌면서 배열에 카드 값을 넣어주면 기본적인 준비는 끝이다.

 

 

 

int card;
int maxSet = 0;
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++){
            card = arr[i]+arr[j]+arr[k];
            if(card <= m && maxSet < card) maxSet = card;
        }
    }
}
cout << maxSet;

카드의 합을 구할 정수변수 card를 만들고, 문제에서 원하는 m을 넘지 않으면서 m에 가장 가까운 카드 셋을 저장해줄 maxSet 변수를 만들어 0으로 초기화해준다. 그 후엔 단순하다. 3장의 카드 조합을 찾아야 하므로 삼중 for문으로 해결하면된다. 이때 3장의 카드는 겹치지 않으므로 인덱스에 주의하자.

인덱스에 주의해 세 개의 카드를 뽑아 합을 card에 저장해주고 maxSet, m과 비교하며 정답에서 원하는 카드셋을 찾아주면 된다. 모든 인덱스를 탐색한 후엔 구한 값을 출력하면 끝!

 

 

 

 

 

---

 

 

 

2798번: 블랙잭