Level 1. 삼총사

Level 1. 삼총사

 

 

next_permutation() 함수는 현재 순열의 다음 순열을 만든다.

 

1, 2, 3, 4의 경우

• 1, 2, 4, 3
• 1, 3, 2, 4
• 1, 3, 4, 2
• 1, 4, 2, 3
• ...

 

 

비트마스크에 순열을 적용하면 조합을 만들 수 있다.

 

4개 중 2개를 뽑을 경우

• 0, 0, 1, 1
• 0, 1, 0, 1
• 0, 1, 1, 0
• 1, 0, 0, 1
• ...

 

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

using namespace std;

int solution(vector<int> number)
{
    int answer = 0;

    vector<int> comb(number.size() - 3, 0);
    comb.insert(comb.end(), {1, 1, 1});

    do
    {
        int sum = 0;
        auto it = comb.begin();

        while ((it = find(it, comb.end(), 1)) != comb.end())
            sum += number[it++ - comb.begin()];

        answer += !sum;
    }
    while (next_permutation(comb.begin(), comb.end()));

    return answer;
}