본인 코드

#include <bits/stdc++.h>
using namespace std;
int n, w;
map<string, vector<string>> wear;
string c, k;
int sel, sum;
vector<int> wearnum;
vector<int> v;
vector<int> ret;

void combination(int start, vector<int> b)
{
    if(b.size() == sel){
        int mult = 1;
        for (int num : b){
            mult *= wearnum[num];
        }
        sum += mult;
    }

    for (int i = start + 1; i < sel; i++){
        b.push_back(i);
        combination(i, b);
        b.pop_back();
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    for (int i = 0; i < n; i++){
        cin >> w;

        // 의상 수가 0이면 0일 출력
        if(w == 0){
            ret.push_back(0);
            continue;
        }

        sum = 0;
        wearnum.clear();
        wear.clear();
        v.clear();
        for (int j = 0; j < w; j++)
        {
            // c: 옷
            // k: 종류
            cin >> c >> k;

            wear[k].push_back(c);
        }

        for(auto it: wear){
            wearnum.push_back(it.second.size());
        }

        // wearnum -> [2, 3, 1] 종류별 옷의 갯수가 저장되어 있음
        // 조합 1. - 한 부위만 걸치는 경우 - 각 부위별 옷의 종류 하나씩 더함
        for(int num : wearnum){
            sum += num;
        }

        // 조합 2. - 몇 부위만 선택해서 걸치는 경우 - 선택된 부위별 종류의 수를 곱해줘야됨.
        for (int x = 2; x < wearnum.size() - 1; x++){
            sel = x;
            combination(-1, v);
            v.clear();
        }

        // 한 부위만 있는 경우 - 이미 고려했으므로 로직 중복
        // 두 부위 이상인 경우 - 각 부위별로 순회하며 하나씩 선택되는 경우 더하기
        if(wearnum.size() == 1){
            ret.push_back(sum);
            continue;
        }else{
            int mult = 1;
            for(int num : wearnum){
                mult *= num;
            }
            sum += mult;
            ret.push_back(sum);
        }
    }

    for(int num: ret){
        cout << num << "\n";
    }

    return 0;
}

1. 솔직히 무슨 개짓거리를 해놓은지 모르겠음
2. 경우의 수를 다 따져서 조합으로 처리했음
   1. 각 부위당 하나만 입고 나머지 안입는 경우
   2. 어떤 부위를 입을지 고르고 선택한 부위들에 대한 가짓수만 곱한다. 나머지는 안입음
   3. 모두 다 입는 경우

위의 세 가지 경우를 모두 곱했다. - 시간초과

개선 코드

각 부위에 안입는 경우를 추가하여 가짓수를 각각 모두 곱하고, 전부다 안입는 경우만 빼주면 됨.

아래는 로직 이해 후 직접 작성해본 코드.

#include <bits/stdc++.h>
using namespace std;
int n, w;
vector<int> ret;
vector<int> wearnum;
map<string, vector<string>> mp;

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

    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> w;
        mp.clear();
        wearnum.clear();
        for (int j = 0; j < w; j++)
        {
            string wear, kind;
            cin >> wear >> kind;

            mp[kind].push_back(wear);
        }

        for(auto it : mp){
            wearnum.push_back(it.second.size() + 1);
        }

        int mult = 1;
        for (int n : wearnum){
            mult *= n;
        }
        ret.push_back(mult - 1);
    }
    for(int n : ret){
        cout << n << "\n";
    }
    return 0;
}

아래는 모범답안이다. 차이점은 wearnum이라는 변수를 굳이 생성하지 않고 가짓수 숫자 Int형으로 Map을 구성했다는 것이다.

#include <bits/stdc++.h>
using namespace std;
int t,n;
string a, b;

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

    cin >> t;
    while(t--){
        map<string, int> _map;
        cin >> n;

        for (int i = 0; i < n; i++){
            cin >> a >> b;
            _map[b]++;
        }
        long long ret = 1;
        for(auto c : _map){
            ret *= ((long long)c.second + 1);
        }
        ret--;
        cout << ret << "\n";
    }
    return 0;
}