프로그래머스 스킬 체크 (레벨2) - 조합 문제

프로그래머스 스킬 체크 문제를 푸는데

조합 관련 문제가 나왔다.

가능한 모든 조합의 곱들의 합을 구해야 하는데

시간만 많으면 직접 라이브러리를 만들 수 있겠지만

테스트 시간 안에는 불가능했다.

 

구글링을 해서

크기가 n인 벡터에서 r개의 요소를 골라낸 벡터들을 리턴해주는 소스를 얻어냈다.

#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> Combination(vector<int> container, int r) {
    int n = container.size();
    if (n < r) return {};
    if (r < 0) return {};

    vector<vector<int>>totVec;//return 2d-vector
    vector<int> tempVec(r);//saves temporary combination

    vector<bool> v(n);
    fill(v.end() - r, v.end(), true);
    int idx;
    do {
        idx = 0;
        for (int i = 0; i < n; ++i) {
            if (v[i]) {
                tempVec[idx++] = *(container.begin() + i);
            }
        }
        totVec.push_back(tempVec);
    } while (next_permutation(v.begin(), v.end()));

    return totVec;
}

vector<int> v;
int n = v.size();
int ans = 0; // 조합의 곱들의 합
for(int r = 0; r <= n; r++){
    for (auto& vec : Combination(v, r)) {
        int mul = 1;
        for (auto& ele : vec){ // vec = n개 중 r개를 골라낸 벡터
        	mul *= ele;
        }
    	ans += mul;
    }
}

1개의 테스트 케이스만 시간 초과가 나고

나머지는 모두 맞출 수 있었다.

 

출처 : whiteherv.tistory.com/2