[백준 9375] 패션왕 신혜빈

#1 조건.

[입력]

첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.

• 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
• 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.

모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.

[출력]

각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.

#2. 사고과정

최대값 최소값 확인. 테스트케이스 최대 100, 의상 수는 30

의상의 종류가 중요. 근거 : 같은 종류의 의상은 하나만 입을 수 있음. 이말은 이름이 달라도 종류가 같으면 하나로 친다. 

해빈이가 알몸만 아니면 된다는 것이 중요 : 3종류가 있을 때 1종류만 입고 2종류는 입지 않아도 케이스에 포함된다. 다 벗었을 때의 한가지 케이스만 빼주면 된다. 

 

#3. 코드

// n개의 케이스가 주어질 것을 첫번째 줄에 알려줌
// 각 케이스 마다 아이템이 몇개인지 갯수를 알려줌
// 그 후 케이스마다 아이템과 해당 아이템의 종류가 " "을 기준으로 제공됨

#include<bits/stdc++.h>
using namespace std;

int n, m; 
string it, ity;
// 종류만 체크하면 됨으로 키값의 중복이 허용되지 않는 map을 사용
map<string,int> _map ;
int main(){

    cin >> n;   
    for ( int i = 0; i < n; i++ ){
        cin >> m;

        for ( int j = 0 ; j < m; j++ ){
            // 맵에는 타입만 저장하고 같은 타입이 또 존재할 경우 + 1을 해준다. 
            cin >> it >> ity;
            _map[ity] += 1;
        } 
    
    long long result = 1;
    // 모든 종류의 갯수가 파악되면 맵에 있는 값을 하나씩 꺼낸다. 그리고 아무것도 입지 해당 종류의 옷을 입지 않았을 경우도 1가지 포함하여 곱해나간다. 
    // 만약 바지 : 2
    //     상의 : 2
    //     목도리 : 2 라고 가정해보자. 
    // 총 경우의 수는 모두 곱한 8이다. 하지만 빠트릴 수 있는 경우는 입지 않은 경우이다. 그래서 각 종류에 아무것도 입지 않는 것을 하나의 의상으로 하고 추가한다.
    // 총 경우이 수는 3 * 3 * 3 이되고 벌거숭이는 용납하지 않으니 -1을 빼준다. 
    for ( auto a : _map){
        result *= ((long long)a.second + 1); // 옷을 안입는 경우를 한가지씩 추가한다. 
    }
    cout << result - 1 << "\n";
    _map.clear();
    }
    return 0;
}