글 읽기 - 조합을 구해서 풀었더니 시간 초과

ynifamily3 4년 전 0

더 빠른 방법이 존재하나요?

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;
int N;

int main(void)
{
    // int N;
    vector<int> arr;
    cin >> N;
    for (int i = 0; i < 2 * N - 1; i++)
    {
        int d;
        cin >> d;
        arr.push_back(d);
    }
    vector<int> ind;

    int k = N;
    for (int i = 0; i < k; i++)
    {
        ind.push_back(1);
    }

    for (int i = 0; i < arr.size() - k; i++)
    {
        ind.push_back(0);
    }
    sort(ind.begin(), ind.end());

    do
    {
        int sum = 0;
        vector<int> store;
        for (int i = 0; i < ind.size(); i++)
        {
            if (ind[i] == 1)
            {
                sum += arr[i];
                store.push_back(arr[i]);
            }
        }
        if (sum % N == 0)
        {
            for (int j = 0; j < store.size(); j++)
            {
                cout << store[j] << " ";
            }
            cout << endl;
            return 0;
        }
    } while (next_permutation(ind.begin(), ind.end()));
    return 0;
}
// N의 배수여야 한다.
// 2N-1개에서 N 개를 고르는 '조합'

ho94949 4년 전 0

수가 최대 500개 까지 있을 수 있으니 999개에서 500개를 고르는 겅우의 수는 너무 큽니다. 더 빠른 방법이 존재합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

조합을 구해서 풀었더니 시간 초과

ynifamily3 4년 전 0

ho94949 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말