Level 2. 시소 짝꿍

Level 2. 시소 짝꿍

 

 

모든 사람 중 2명을 뽑는 조합을 구하고, 각 조합에서 나온 모든 토크를 set에 넣어 중복이 있는지 확인한다.

 

하지만, 시간 초과 발생..

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

vector<vector<bool>> get_comb(int n, int r)
{
    vector<vector<bool>> result;
    vector<bool> comb(n, 0);

    fill_n(comb.rbegin(), r, 1);

    do
        result.emplace_back(comb);
    while (next_permutation(comb.begin(), comb.end()));

    return result;
}

long long solution(vector<int> weights)
{
    long long answer = 0;
    size_t n = weights.size();
    vector<vector<int>> newtons(n);

    for (int i = 0; i < n; ++i)
    {
        newtons[i].emplace_back(weights[i] * 2);
        newtons[i].emplace_back(weights[i] * 3);
        newtons[i].emplace_back(weights[i] * 4);
    }

    for (vector<bool>& comb : get_comb(n, 2))
    {
        set<int> st;

        for (int i = 0; i < n; ++i)
        {
            if (comb[i])
            {
                st.emplace(newtons[i][0]);
                st.emplace(newtons[i][1]);
                st.emplace(newtons[i][2]);
            }
        }

        answer += (st.size() < 6);
    }

    return answer;
}

 

여러 개의 원소가 같은 자리를 차지하려는 상황이고 그 중 중복을 검사하는 문제이므로, 배열을 만들어 다 때려넣는 방식을 생각해 볼 수 있다.

• 이 때 앞에서부터 차례로 확인하면 중복되는 경우 없이 DP를 이용할 수 있다.

 

내가 들어가려는 자리에 이미 숫자가 있다면, 그 숫자는 모두 다른 몸무게에서 비롯된 것들이므로 그냥 더해줘도 된다.

• 이 문제에서는 100, 100 같이 완전히 같은 숫자가 예외인 상황이므로, 몸무게만 별도로 관리하는 벡터 W를 만들어 *2, *3, *4 3개 중 2개를 빼주면 1개로 처리할 수 있다.

 

#include <iostream>
#include <vector>

using namespace std;

long long solution(vector<int> weights)
{
    long long answer = 0;
    vector<int> W(1001), N(4001);

    for (int w : weights)
    {
        int w2 = w * 2, w3 = w * 3, w4 = w * 4;

        answer += N[w2] + N[w3] + N[w4] - W[w] * 2;

        ++N[w2], ++N[w3], ++N[w4], ++W[w];
    }

    return answer;
}