9375번: 패션왕 신해빈

문제링크

C++

#include <iostream>
#include <unordered_map>

using namespace std;

int T;
unordered_map<string, int> my_map;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;

    for (int i = 0; i < T; i++)
    {
        int n;
        cin >> n;
        string tmp1, tmp2;
        my_map.clear();
        for (int j = 0; j < n; j++)
        {
            cin >> tmp1 >> tmp2;
            if (my_map.count(tmp2) == 0)
            {
                my_map[tmp2] = 1;
            }
            else
            {
                my_map[tmp2]++;
            }
        }
        int ret = 1;
        for (auto i = my_map.begin(); i != my_map.end(); i++)
        {
            ret *= (i->second + 1);
        }
        cout << ret - 1 << "\n";
    }

}

• unordered map 사용
• $O(n)$
• 특정 종류의 의상이 x개 있다면 선택하지 않는 한 가지 선택과 x개 중 한 개를 고르는 x개의 선택이 존재한다.
  • 따라서 한 가지 종류의 의상마다 x+1개의 선택이 가능
• 의상 종류마다 가능한 선택지를 연속해서 곱해주면 모든 가능한 선택의 경우의 수가 나온다.
• 마지막으로 아무 옷도 고르지 않는 경우 한 가지를 빼준다.