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

문제

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

풀이

아예 감을 못 잡아서 솔루션 찾아봤는데 map을 이용한 사람들이 많았고, 어떤 사람이 진짜 천재같이 간단하게 풀어서 그 방식으로 풀어봤다.

weights[i] 사람의 짝꿍을 찾고 싶으면 weights[i]:x = (2:3 or 2:4 or 3:4)에 해당하는 x를 찾으면 됨
또한, 몸무게가 같은 사람이 짝꿍이 될 수도 있음

• cnt 배열에 각 몸무게 별 개수 세어주기
• weights 배열을 하나씩 확인하면서 (2:3), (2:4), (3:4) 비율에 해당하는 값 base 찾아주기
• 정답에 cnt[base] 더해주기 //cnt[base]가 0이라면 안 더해지고, 1이면 더해지는 것 !
• 몸무게가 같은 사람의 경우는 조합을 이용해서 경우의 수 세어주기

  몸무게가 같은 사람이 3명이라면 2명만 시소 태워야하므로 n명 중에 2명 뽑는 경우의 수
  

코드

#include <string>
#include <vector>

using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    vector<long long> cnt(1001, 0); //몸무게 별 개수
    
    for(int i=0; i<weights.size(); i++)
        cnt[weights[i]]++;
    
    for(int i=0; i<weights.size(); i++) {
        //2:3
        if(weights[i] % 2 == 0) {
            long long base  = (weights[i]/2) * 3;
            if(base <= 1000)    answer += cnt[base];
        }
        //3:4
        if(weights[i] % 3 == 0) {
            long long base  = (weights[i]/3) * 4;
            if(base <= 1000)    answer += cnt[base];
        }
        //1:2
        long long base  = weights[i] * 2;
        if(base <= 1000)    answer += cnt[base];
    }

    /* 몸무게 같은 경우 처리 */
    for(int i=100; i<=1000; i++) {
        if(cnt[i] >= 2)
            answer += (long long)(cnt[i] * (cnt[i]-1)) / 2; //n개 중에 2개 뽑는 경우의 수 : n(n-1) / 2
    }
    
    return answer;
}