백준 2798 블랙잭 - C++

접근

N 개의 카드 중에서 3개의 카드를 뽑아 그 합이 M과 같거나 근접한 경우를 구해야 한다.

이번 문제는 뽑는 카드의 개수가 3개로 정해져 있어서 3중 for문으로 풀 수도 있지만 재귀문을 사용해도 된다.

성능은 조건만 잘 맞춰주면 3중 for문이 더 빠르긴 하다.

N이 5라 할 때 처음 뽑을 수 있는 카드의 수는 5 그다음은 4 다음은 3이다. 

카드의 개수는 N에 영향을 받으니 식으로 나타내면  N x (N-1) x (N-2)이다.

 

 

#include <iostream>
#include <vector>
using namespace std;
int possibleCnt = 3, totalSum=0;
int N, M;
vector<int> nums;
void re(int idx, int start, int sum){
    if(idx == possibleCnt) {
        if(sum > totalSum && sum <= M) totalSum = sum;
        return;
    }
    
    for(int i=start; i<N; i++){
        re(idx+1, i+1, sum+nums[i]);
    }
    return;
}

int main(){
    cin >> N >> M;
    int num;
    for(int i=0; i<N; i++){
        cin >> num;
        nums.push_back(num);
    }
    re(0,0,0);
    cout << totalSum << '\n';
    return 0;
}