(2798) 블랙잭

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

단계별로 풀어보기

12단계(브루트 포스) 1번째

 

 

 

브루트 포스 단계이므로 당연하다면 당연하지만 n의 범위가 100이므로 카드 3장의 조합을 전부 확인하는 O(n^3) 알고리즘이면 풀면 충분하다.

보통 브루트 포스를 하기 전에는 시간 복잡도와 범위를 고려하여 시간초과가 날지 계산을 해야 하겠지만 어차피 브루트 포스 단계라 시간초과가 되지 않을 것이 자명하므로 앞으로는 생략한다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  int n, m, ans= 0;
  
  cin >> n >> m;
  
  vector<int> v(n);
  
  for(int i=0;i<n;i++)  cin >> v[i];
  
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      for(int k=j+1;k<n;k++){
        if(v[i]+v[j]+v[k]>m)  continue;
        
        ans= max(ans, v[i]+v[j]+v[k]);
      }
    }
  }
  
  cout << ans;
  
  return 0;
}