[백준] 9375번

단순한 알고리즘이다.

중학생때인가 고등학생 때 배운 알고리즘을 이용하면 된다.

모자를 안쓴다, 쓴다, 

로 구분이 되고 모자들은 모두 다른 모자들이기 때문에 n+1개다.

마찬가지로 다른 종류들고 그렇다.

거기에 문제에서 말한 알몸이 아닌 상태만 뜻하면 되는 듯하다. 그렇다면 -1을 빼주면 된다.

 

정말 간단한 알고리즘이지만 우리 claude 형님이 알려줬다. 내가 4시간 동안, 머리에 희미하게 남아있는 combination을 최대한 이용해서 해결하려고 했는데 걍 멍청한듯하다..

#include <map>
#include <iostream>
#include <locale>
#include <sstream>
#include <vector>

std::map<std::string, int> dict; // type name

int countWay();

int main() {
    int t, n;
    std::ostringstream buffer;
    std::cin >> t;
    for (int i = 0; i < t; i++) {
        std::cin >> n;
        std::string type;
        dict.clear();
        int sum = 1;
        for (int j = 0; j < n; j++) {
            std::cin >> type >> type;
            dict[type] += 1;
        }
        for (const auto& pair : dict) {
            sum *= (pair.second+1);
        }
        buffer << sum-1 << std::endl;
    }
    std::cout << buffer.str();
    return 0;
}