#2798. 블랙잭

• N장의 카드
• M : 목표
• N장의 카드 중 3개 선택
• 3개의 숫자 합이 M에 최대한 가깝도록(M을 넘어서면 안됨)

N은 최대 100이기에 100장 중 3장을 선택하는 경우의 수 100 x 99 x 98 = 970,200‬가 최대이다.
그러므로 충분히 모든 경우의 수를 구해 답을 찾아낼 수 있는 문제이다.

재귀나 for문을 이용하여 풀 수 있을 것이다.

필자는 재귀를 사용하였다.

M은 최대 300000이기에 MAX 값으로 두었고 재귀의 내용은 다음과 같다.

• 매개변수
  • numbers : N개의 숫자를 담을 vector
  • goal : M
  • ans : 숫자 합
  • index : numbers의 인덱스
  • selected : 남은 카드 선택 횟수
• 실패 조건
  • 숫자 합이 M보다 클 때
  • index가 numbers의 크기를 넘었을 때
• 성공 조건
  • 3번을 뽑았을 경우, goal과 ans의 차이가 최소인 값
• 재귀함수
  • 카드를 선택하지 않을 때
  • 카드를 선택했을 때
    ans에 선택한 카드가 더해짐

    #include <iostream>
    #include <vector>
    #define MAX 300000;
    using namespace std;
    int min_diff = MAX;
    vector<int> numbers;
    void doCombination(vector<int> numbers, int goal, int ans, int index, int selected) {
        if(ans > goal) return;
        if(selected == 0) {
            min_diff = min_diff > goal-ans ? goal-ans : min_diff;
            return;
        }
        if(index >= numbers.size()) {
            return;
        }
        doCombination(numbers, goal, ans, index+1, selected); // not selected
        ans += numbers[index];
        doCombination(numbers, goal, ans, index+1, selected-1); // selected
    }
    int main() {
       int n, m, answer = 0;
       cin >> n >> m;
       numbers.resize(n);
       for(int i = 0; i < n; ++i) {
           cin >> numbers[i];
       }
       doCombination(numbers, m, 0, 0, 3);
       answer = m - min_diff;
       cout << answer << endl;
       return 0;
    }