[백준] 9375번*

💻 C++ 기반

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

✔️ 모든 조합을 어렵게 구하지 않아도 된다
✔️ 각 type마다 선택하는 경우(O)/선택하지 않는 경우(X)가 있다
✔️ 마지막에 모든 type을 다 선택하지 않는 경우(X)를 빼준다
✔️ unordered_map은 사실상 각 type 별로 몇 개의 name이 있는지 저장하기 위한 용도

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tc;
    cin >> tc;
    while (tc--)
    {
        int n;
        cin >> n;

        unordered_map<string, int> m;
        int cnt = 1;
        for (int i = 0; i < n; i++)
        {
            string name, type;
            cin >> name >> type;
            m[type]++;
        }

        unordered_map<string, int>::iterator idx;
        for (idx = m.begin(); idx != m.end(); idx++)
        {
            cnt *= idx->second + 1;
        }

        cout << cnt - 1 << '\n';
    }

    return 0;
}

좋은 웹페이지 즐겨찾기