[구현 / BOJ 9375 / C++] 패션왕 신해빈

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

1) map 자료구조를 활용한다.
2) 해당 옷종류를 카운팅한다.
3) 옷종류를 카운팅한 값 + 1 한 값을 모두 곱해주고, 1을 빼준다.

이 문제의 핵심은 두 가지가 있다.

첫번째로 같은 이름을 가진 의상이 존재하지 않는다고 했으므로 'AAA 모자', 'BBB 모자' 를 입력받는다면, 모자 * 2종류 라고 이해할 수 있다. 즉, map<string, int>로 이해할 수 있다. (모자 : 2)

 

두번째로 의상을 입을 수 있는 경우의 수를 구하는 방법이다. 예를 들자면, 'AAA 모자, BBB 모자, CCC 안경' 이라고 하자. 그렇다면 입을 수 있는 총 경우의 수는 'AAA 모자 + CCC 안경, BBB 모자 + CCC 안경, CCC안경, AAA 모자, BBB 모자' 이다.

즉 가만히 생각해보면 {AAA 모자, BBB 모자, 모자안씀} * {CCC 안경, 안경안씀} 으로 표현해줄 수 있고, 개수를 구하면 3가지 * 2가지 - 1가지(모자안씀, 안경안씀) = 5가지로 구할 수 있다.

 

(AAA종류의 개수 + 1) * (BBB종류의 개수 +1) * ...... (ZZZ종류의 개수 +1) - 1 = (의상을 입을 수 있는 총 경우의 수)

#include <bits/stdc++.h>
#define ll long long

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--){
        cin >> N;
        map<string, int> closet;
        while(N--){
            cin >> a >> b;
            closet[b]++;
            
        }
        
        ll ans=1;
        for(auto i : closet) ans *= ((ll)i.second+1);
        cout << ans-1 << '\n';
    }
}