9375번 패션왕 신해빈

수학, 자료구조, multimap

 

https://www.acmicpc.net/problem/9375

 

 

각 Type에 Name을 담는다.

 

이때, 숫자가 아닌 문자열이고, 1개 초과로 담아야 하므로, multimap을 이용한다.

 

정답은 (각 Type에 속해 있는 Name의 개수 + 1)을 Type 수에 맞게 연산한다.

 

 

#include<bits/stdc++.h>

using namespace std;

int T, n;
multimap<string, string> mm;
set<string> st;

int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin);
    cin.tie(0);

    scanf("%d", &T);

    while (T--)
    {
        cin >> n;

        st.clear();
        mm.clear();

        string Name, Type;
        for (int i = 0; i < n; i++) {
            cin >> Name >> Type;
            mm.insert(make_pair(Type, Name));
            st.insert(Type);
        }

        int ans = 1;

        for (auto it = st.begin(); it != st.end(); it++) {
            ans *= (mm.count(*it) + 1);
        }

        printf("%d\n", ans - 1);
    }

    return 0;
}