[백준 9375] 패션왕 신해빈

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

 

경우의 수를 찾는 문제

 

아래 케이스를 살펴보자.

 

옷의 종류가 3가지이고

a라는 부위가 3개, b라는 부위가 2개, c라는 부위가 1개라고 가정하면

총 가능한 경우의 수는

1가지를 고를 때

a + b + c개

2가지를 고를 때

ab + ac + bc

3가지를 고를 때

abc

이면 총 경우의 수는 위 3가지를 더한 abc + ab + ac + bc + a + b + c가 된다

 

이를 일반화 하기 위해 인수분해를 해 보면

a(bc + b + c + 1) + bc + b + c가

되며 bc + b + c + 1꼴로 만들기 위해 a(bc + b + c + 1) + bc + b + c + 1 - 1로 만든다. bc + b + c + 1 = k로 치환하면

ak + k - 1이 되고 k(a + 1) - 1이 되는데 k = b(c + 1) + (c + 1)이 되고 다시 c + 1로 인수분해 하면 (c + 1)(b + 1)이 되고 최종적으로 도출된 식은 (a + 1)(b + 1)(c + 1) - 1이 된다.

 

위 결과를 이용해 옷의 종류가 n가지라 치면

(1번째 종류의 수 + 1) * (2번째 종류의 수 + 1) * ... * (n번째 종류의 수 + 1) - 1 이 정답이 된다

#include <bits/stdc++.h>
#define ll long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
using namespace std;
int main() {
    FASTIO
    int t; cin >> t;
    while(t-->0) {
        int n; cin >> n;
        map<string, int> hmap;
        for(int i = 0; i < n; i++) {
            string a, b; cin >> a >> b;
            if(hmap[b] == 0) {
                hmap[b] = 1;
            } else {
                hmap[b]++;
            }
        }
        int res = 1;
        for(auto &current : hmap) {
            res *= (current.second + 1);
        }

        cout << res - 1 << '\n';
    }
}