백준 2798번 - 블랙잭

https://www.acmicpc.net/problem/2798

DFS를 이용하여 완전탐색을 진행하면 된다.

문제가 구현으로 분류되어 있어 시뮬레이션 카테고리에 넣었는데

다음 순열등 다양한 방법으로 문제를 해결할 수 있다.

N개의 카드중에 3개를 고른 후에 M보다 크지않을때 최대값을 찾으면 답을 구할 수 있다.

N의 크기가 100이 최대 이기 때문에 O(N^3)의 시간안에 풀 수 있다.

#include <iostream>
#include <vector>
using namespace std;
 
int N,M;
int ans=0;
vector<int> vec;
 
void dfs(int pos,int cnt,int sum){
    if(cnt==3){
        
        if(sum<=M)
            ans=max(ans,sum);
        
        return;
    }
    
    if(sum>M || pos>=N)
        return;
    
    dfs(pos+1,cnt+1,sum+vec[pos]);
    dfs(pos+1,cnt,sum);
}
int main() {
    
    cin>>N>>M;
    vec=vector<int> (N,0);
    
    for(int i=0;i<N;i++)
        scanf("%d",&vec[i]);
    
    dfs(0,0,0);
    cout<<ans<<endl;
    return 0;
}