[BOJ] 2798번 "블랙잭" (C++/Swift)

2798번 블랙잭

 

문제 다 읽을 필요도 없다.

카드를 고르는 것이기 때문에, 카드 세 장을 골랐을 때 세 장의 카드는 모두 달라야한다는 생각 하나만 가지고

브루트포스하게 문제를 풀면 된다. (숫자가 겹치면 안된다는 것이 아님)

 

간단히 3중 for문으로 해결 가능하다.

 

아래 코드에서처럼, O(n^3) 의 시간복잡도 내에 문제 해결 가능한데

주어진 n은 많아야 100개

최악의 경우에도 주어진 1초를 넘지 않는다.

 

C++

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

int n,m,sum,ans;
int arr[100];

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin>>n>>m;
    for(int i=0; i<n; i++) {
        cin>>arr[i];
    }

    for(int i=0; i<n-2; i++){
        for(int k=i+1; k<n-1; k++) {
            for(int j=k+1; j<n; j++) {
                sum = arr[i]+arr[j]+arr[k];
                if(m>=sum) { ans = max(ans,sum); }
            }
        }
    }
    cout<<ans;
}

 

Swift

import Foundation

var n: Int = 0
var m: Int = 0
var cards: [Int] = []

func main() {
    let input = readLine()!.components(separatedBy: " ").map { Int($0)! }
    cards = readLine()!.components(separatedBy: " ").map { Int($0)! }
    n = input[0]
    m = input[1]
    
    var answer: Int = 0
    
    for i in 0...n-3 {
        for j in i+1...n-2 {
            for k in j+1...n-1 {
                let sum = cards[i]+cards[j]+cards[k]
                if sum <= m { answer = max(answer, sum) }
            }
        }
    }
    
    print(answer)
}

main()