[백준 9375] 패션왕 신해빈

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

 

간단하면서도, 생각보다 어려웠던 문제.

 

같은 종류의 옷은 한 번만 사용할 수 있다.

여기서는 종류가 중요하지, 그 옷의 이름은 중요하지 않다.

 

# 모자가 1개라면?

(모자 착용), (모자 미착용) = 2가지

신해빈은 무조건 하나의 옷은 착용해야 하므로 마지막 미착용의 경우의 수는 빼야 한다.

2 - 1 = 1가지.

 

# 모자가 2개라면? 

같은 종류의 옷은 못 입는다고 하였으니,

(모자 A) (모자 B) (모자 미착용) = 3가지

신해빈은 무조건 하나의 옷은 착용해야 하므로 마지막 미착용의 경우의 수는 빼야 한다.

3 - 1 = 2가지.

 

# 모자가 2개이고, 렌즈가 1개라면?.

(모자A, 렌즈 미착용)

(모자 B, 렌즈 미착용)

(모자 미착용, 렌즈 착용)

(모자 A, 렌즈 착용)

(모자 B, 렌즈 착용)

(모자 미착용, 렌즈 미착용)

신해빈은 무조건 하나의 옷은 챙겨야 하기 때문에 아예 입지 않는 경우를 1개 빼야 한다.

6 - 1 = 5가지

 

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int t, n, ans = 1;
string s1, s2;
map<string, int> mp;
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        mp.clear();
        for (int i = 0; i < n; i++)
        {
            cin >> s1 >> s2;
            mp[s2]++;
        }
        
        ans = 1;
        for (auto item : mp)
        {
            ans *= (item.second + 1);
        }
        
        cout << ans - 1 << '\n';
    }
    return 0;
}