[BOJ 2798] 블랙잭 (C++)

www.acmicpc.net/problem/2798

2798번: 블랙잭

블랙잭 문제

구현 방법

이 문제는 쉬운 편에 속하는 완전 탐색(Brute Force) 문제입니다.

완전 탐색에 익숙하지 않아 문제를 해결하는데 고민을 좀 했습니다.

 

구현 방법은 다음과 같습니다.

• 3중 for문을 돌면서, n개의 카드 숫자 중 가능한 모든 조합으로 합을 구한다.
• 그 합이 목표 점수, 즉 m 보다 작거나 같으면, pair <총합, (m - 총합)의 절댓값>을 저장한다.
• m-총합의 절댓값, 즉 목표 점수와의 차이가 제일 적은 것을 출력한다.

 

1) 3중 for문 돌면서 가능한 모든 조합 구하기

 

3중 for문을 돌면서 가능한 모든 조합을 구할 때, 유의해야 하는 것이 있습니다.

예를 들어 다음과 같이 10개의 숫자가 있다고 생각해봅시다.

index	1	2	3	4	5	6	7	8	9	10
숫자	7	19	5	10	12	4	5	15	2	17

10개의 숫자에서 3개를 선택해 가능한 모든 경우의 수를 구하면, 보통 사람들은 다음과 같은 선택을 합니다.

 

 

1번째 수, 2번째 수, 3번째 수

1번째 수, 2번째 수, 4번째 수

1번째 수, 2번째 수, 5번째 수

...

1번째 수, 2번째 수, 10번째 수

 

 

1번째 수, 3번째 수, 4번째 수

1번째 수, 3번째 수, 5번째 수

1번째 수, 3번째 수, 6번째 수

...

1번째 수, 3번째 수, 10번째 수

 

잘 보시면 3중 for문을 어떻게 코딩해야 할지 아시겠나요??

 

첫 번째 선택할 숫자는 0번째 ~ n-2번째,

두 번째 선택할 숫자는 첫 번째 숫자 다음번째 ~ n-1,

세 번째 선택한 숫자는 두 번째 숫자 다음번째 ~ n

 

 

2) 그 합이 목표 점수, 즉 m 보다 작거나 같으면, <총합, (m - 총합)의 절댓값>을 저장한다.

 

pair를 만들 때 첫 번째에는 총합, 두 번째에는 (목표수-총합)의 절댓값을 계산해 가장 가까운 숫자를 저장합니다.

 

예를 들어 목표가 21이고, 총합이 20이면 (m-총합)의 절댓값은 1이고, 목표가 21이고 총합이 17이면 (m-총합)의 절댒값은 4입니다.

 

이렇게 저장해놓고 마지막에 (목표수-총합)을 기준으로 오름차순으로 정렬하면, 목표수에 가장 가까운 총합을 구할 수 있습니다.

 

위의 방법을 아래처럼 구현했습니다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n,m; 
    int sum;
    vector<int> v;
    
    cin >> n >> m;
	
    //숫자 카드 입력 받기
    for(int i=0;i<n;i++) {
        int num; cin >> num;
        v.push_back(num);
    }
    //<총합, 목표 점수와의 차이> pair 저장할 벡터 ans
    vector<pair<int, int>> ans;

    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 = v[i] + v[j] + v[k];
                
                //만약 총합이 목표 점수와 같거나 작을때
                //<총합, 목표 점수와의 차이>를 push
                if(sum <= m)
                	ans.push_back({sum, m-sum});
            }
        }
    }
	
    //목표 점수와 차이를 오름차순으로,
    //즉 목표 점수와 차이가 제일 적은게 앞으로 온다.
    sort(ans.begin(), ans.end(), cmp);

	//첫번째 원소 출력
    cout << ans[0].first;
}