백준 9375 (패션완 신해빈) c++

문제

9375번: 패션왕 신해빈

옷의 종류가 n개 주어지면 종류가 겹치지 않는 선에서 아무것도 입지 않은 상태를 제외한 경우의 수를 구하는 문제

입니다.

예를 들어 n = 3이고 옷의 종류가 다음과 같이 주어지면

hat headgear
sunglasses eyewear
turban headgear

 

(hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses) 와 같이 5가지의 경우의 수가 나올 수 있습니다.

 

따라서 다른 종류끼리 조합을 생각해 보아야 합니다.

위의 예시를 보면 

<headgear>

hat

turban

 

<eyewear>

sunglasses

 

1개의 옷만 입을경우

{hat}, {turban}, {sunglasses}

 

2개의 옷을 입을경우

{hat, sunglasses}, {turban, sunglasses}

 

이를 살펴보면 종류가 같으면 조합을 할 수 없으므로 옷의 종류별로 모아 조합을 생각해야합니다.

<headgear> 에서의 옷을 선택할 가지수는 총 3가지 입니다. {hat}, {turban} 그리고 아예 선택하지 않을 경우의 수를 고려하면 총 3가지가 나옵니다.마찬가지로 <eyewear> 에서는 선택할 가지수는 총 2가지 입니다. {sunglasses} 와 아예 선택하지 않을 경우의 수

 

그렇게 조합의 식을 해보면 3 * 2 = 6이 됩니다.하지만 정답은 5입니다. 다시 생각해보면 우리가 각 종류마다 아예 선택하지 않을 경우의 수도 고려해주었기 때문에 모든 종류마다 옷을 선택하지 않으면 발가벗게 되므로 이러한 경우의 수는 마지막에 1개 빼줘야 합니다.따라서 (3 * 2) - 1 = 5가 됩니다.

 

점화식을 세워 보면 각각의 종류별로 수를 세어 그 수에 1을 더하고 종류별로 곱하고 마지막에 1을 빼주면 됩니다.

우리는 옷의 종류만 필요하므로 옷의 종류를 map에 넣어줍니다. 

map을 중복을 허용하지 않으므로 새로 들어온 종류가 이미 map에 있다면 해다 종류를 ++ 해줍니다.

그 다음 각 종류마다 +1 한 값을 곱해주고 마지막에 1을 빼고 출력해주면 됩니다.

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
map<string, int > m;
int n;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        int cnt = 1;
        cin >> n;
        for (int i = 0; i < n; i++) {
            pair<string, string>p;
            cin >> p.first >> p.second;
            if (m.find(p.second) == m.end())
                m.insert({ p.second,1 });
            else m[p.second]++;
        }
        for (auto iter : m) {
            cnt *= (iter.second + 1);
        }
        cnt--;
        cout << cnt << '\n';
        m.clear();
    }
 
 
    return 0;
}