boj 2798 c++ 블랙잭

boj 2798 c++ 블랙잭

백준 2798 cpp 블랙잭

 

처음 보자마자 next_permutation을 써야겠다고 생각하고 풀었던 문제.

그러나 next_permutation이 너무 중복되는 것이 많아 시간 초과가 떴다.

어이없게도 3중 for문으로 브루트포스 하고 나니 잘 풀렸다.

아래는 정답코드.

 

#include <bits/stdc++.h>
using namespace std;

int arr[101];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int res = -1;

    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> arr[i];
    for (int i = 0; i < N - 2; i++)
    {
        for (int j = i + 1; j < N - 1; j++)
        {
            for (int k = j + 1; k < N; k++)
            {
                int sum = 0;
                sum += arr[i] + arr[j] + arr[k];
                if (sum <= M)
                    res = max(res, sum);
            }
        }
    }
    cout << res;
}

 

아래는 시간초과가 뜬 코드

#include <bits/stdc++.h>
using namespace std;

int arr[101];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int res = 10000000;
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> arr[i];
    do {
        int sum = 0;
        for (int i = 0; i < 3; i++)
            sum += arr[i];
        if (sum <= M)
            res = min(M - sum, res);
    } while (next_permutation(arr, arr + N));

    cout << M - res;
}