[백준 9375] 패션왕 신해빈

🔗알고리즘 문제

실버3 문제이지만 수학을 통한 식 세우기가 조금 어려웠던 문제. 수학은 항상 공부하지만 응용은 언제나 어려운 듯 싶다.

문제 분석

이 문제는 해빈이의 옷장 정보가 주어질 때 해빈이가 옷을 겹치지 않고 알몸이 아닌 채로 입을 수 있는 경우의 수를 구하는 문제이다.

🧢 | hat, turban
🥽 | sunglasses

해빈이의 옷장에 위와 같은 옷들이 있을 때 해빈이는 옷을 hat turban sunglasses hat, sunglasses turban, sunglasses 이렇게 5가지 형태로 입을 수 있다.

발상 & 알고리즘 설계

해빈이가 옷을 입을 때는 같은 종류의 옷을 입는다와 입지 않는다 두 가지 상태로 나타낼 수 있다.

* X -> 옷을 입지 않은 상태를 말한다.

A타입 | a, b, X
B타입 | c, X

위와 같이 a b c가 있는 옷장에 각각 종류의 옷을 입지 않는 경우를 포함하면 해빈이가 옷을 겹치지 않고 입을 수 있는 경우의 수는 6이 나오게 된다. 이 때 우리는 해빈이가 옷을 아무것도 입지 않는 경우는 제외하고 싶으므로 1을 빼주면 정답을 얻을 수 있다.

코드

#include<iostream>
#include<map>
#include<string>
#include<vector>

using namespace std;

int main(){
    int testCase;
    
    cin >> testCase;

    while(testCase--){
        map<string, int> m;
        int n;
        int answer = 1;

        cin >> n;

        for(int i = 0; i < n; i++){
            string type;
            string value;
            cin >> value >> type;
            m[type]++;
        }

        for(auto pair : m){
            answer *= pair.second + 1;
        }        

        cout << answer - 1<< "\n";
    }
}