[완전탐색] BAEKJOON 2798번 '블랙잭' 문제

문제 : www.acmicpc.net/problem/2798

2798번: 블랙잭

문제에서 총 카드의 수가 최대 100개이므로, 완전 탐색을 위해 3중 for문을 사용하면 time complex는 1000000정도 된다.

제한시간이 1초이고, python은 1초에 2천만개의 계산 c++는 1초에 반복문 1억번 까지는 충분하므로 이 문제는 완전탐색으로 해결할 수 있다.

 

 

• 파이썬 코드

n,m = list(map(int, input().split(' ')))
arr = list(map(int, input().split(' ')))

length = len(arr)
result = 0;

for i in range(0, length):
    for j in range(i+1, length):
        for k in range(j+1, length):
            sum = arr[i] + arr[j] + arr[k]
            if sum <= m:
                result = max(sum , result)

print(result)

 

• c++ 코드

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

int main(){
    
    int n,m,tmp,sum,max=0;
    vector<int> v;
    
    cin >> n >> m;
    for(int i = 0 ; i< n ; i++){
        cin >> tmp;
        v.push_back(tmp);
    }
    
    for(int i = 0 ; i< n ; i++){
        for(int j = i+1 ; j< n ; j++){
            for(int k = j+1 ; k< n ; k++){
                sum = v[i] + v[j] + v[k];
                if(max < sum && sum <= m)
                    max = sum;
            }
        }
    }
    
    cout << max << endl;

    return 0;
}