[#9375] 패션왕 신혜빈

#include <iostream>
#include <map>
 
using namespace std;
 
int main() {
    int c;
    cin >> c;
 
    for (int tc = 0; tc < c; tc++) {
        int n;
        cin >> n;
 
        map<string, int> clothes;
 
        for (int i = 0; i < n; i++) {
            string name, type;  //이름, 종류
            cin >> name >> type;
 
            if (clothes.find(type) != clothes.end()) {
                //이미 같은 종류 있으면
                clothes[type] = clothes[type] + 1;
            }
            else {
                //없으면
                clothes[type] = 1;
            }
        }
        int result = 1;
 
        map<string, int>::iterator iter;
        for (iter = clothes.begin(); iter != clothes.end(); iter++) {
            result = result * ((*iter).second + 1);
            //mix = mix * (*iter).second;
        }
 
        if (n == 0)
            cout << 0 << "\n";
        else
            cout << result - 1 << "\n";  //다 안입은 경우인 1개 빼주기
    }
 
    return 0;
}

 

key 값인 종류를 기준으로 중복된 아이템이 들어오나 확인하기 위해서 map 사용

 

처음에는 아이템이 n개면 n + (각 종류 아이템 갯수 곱한 합) 으로 생각했다

예를 들어 아이템이 머리템 2개, 상의템 1개, 하의템 3개 있으면

하나씩 입는 경우 : 6

세개 다 입는 경우 : 2 * 1 * 3

 

근데 세개 다 안입고 의상 중 일부만 입을 수 있으므로 이 방법은 안됨

 

각 종류를 기준으로 가능한 경우의 수는 각 종류의 아이템 갯수 + 1 이다. +1은 그 종류 안 입는경우

따라서 모든 종류에 대해 (각 종류의 아이템 갯수 + 1) 끼리 곱해주고

아무것도 안입은 경우인 1을 빼준다.