[BOJ] C++ 9375 패션왕 신해빈 - 해시 맵 사용하기, 수학

2
3
hat headgear
sunglasses eyewear
turban headgear
3
mask face
sunglasses face
makeup face

answer : 
5
3

---

해빈이의 옷을 종류별로 입을 수 있는 최대 가짓수를 계산하는 문제이다. 알몸은 안되며, 종류별로 착용하지 않을 수도 있다. 확률과 통계 시간에 종종 풀어본 유형의 문제인데, 해빈이 옷이 1번 종류 4개, 2번 종류 2개, 3번 종류 2개가 있다고 하면, 각 종류별로 입지 않는 경우 한 개씩을 추가해서 5 * 3 * 3을 하면 옷을 입지 않는 것을 포함 가능한 모든 조합의 수이다. 여기서 옷을 입지 않는 경우를 빼주면 답이 된다.

 

알고리즘은 이렇게 짜면 되는데, 구현이 문제다. 사실 옷의 이름은 필요가 없다. 종류별로 몇 개가 있는지 세주고 1씩 더해서 곱해주면 된다. 그냥 벡터로 구현하는 것보다 맵을 이용 해서 옷의 종류를 키로 사용한다면 탐색이 빨라 실행 시간이 많이 줄어든다. 해시 맵을 까먹지 말고 항상 사용할 수 있나 고민해 보자.

/** 수학 9375 패션왕 신해빈  **/
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;
    vector<int> res;
    while (T--)
    {
        int n;
        cin >> n;
        map<string, int> m;

        for (int i = 0; i < n; i++)
        {
            string str1, str2;
            cin >> str1 >> str2;
            // 맵에 str2 키가 없다면 추가
            if (m.find(str2) == m.end())
            {
                m.insert({str2, 1});
            }
            else
            {
                m[str2]++;
            }
        }
        int result = 1;
        for (auto x = m.begin(); x != m.end(); x++)
        {
            result *= (x->second + 1);
        }
        res.push_back(result - 1);
    }
    for (auto x : res)
        cout << x << "\n";
}