[ 프로그래머스 ] 시소 짝꿍

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/152996

풀이

---

#include <iostream>
#include <string>
#include <vector>
#include <string>
#include <stack>
#include <cmath>
#include <algorithm> 
#include <map>

using namespace std;

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

    // 거리 2,3,4 에 2명을 배치, 균형을 이루는 경우(무게와 거리 곱이 같은 경우)
    // 제한사항에 weights 범위가 넓으므로, 완전탐색으로는 시간 초과 발생

    sort(weights.begin(), weights.end(), greater<int>());

    for (int i = 0; i < weights.size() - 1; i++)
    {
        for (int j = i + 1; j < weights.size(); j++)
        {
            // 다른 수의 4배가 비교수의 2배보다 작을 경우, 균형을 이루는 경우의 수가 없다.
            if (weights[i] * 2 > weights[j] * 4) break;

            // 2*2, 3*3, 4*4 모두 같으므로, 하나만
            if (weights[i] * 2 == weights[j] * 2) answer++;

            // 같은 거리를 제외한 경우의 수
            else if (weights[i] * 2 == weights[j] * 3) answer++;
            else if (weights[i] * 2 == weights[j] * 4) answer++;
            else if (weights[i] * 3 == weights[j] * 4) answer++;
        }
    }

    return answer;
}