9375

문제 요약

 

패션에 매우 민감하다. 한번 입었던 옷들의 조합을 다시 입지 않는 친구가 있다. 이 친구의 의상이 주어졌을 때 친구가 알몸이 아닌 상태로 며칠 동안 밖에 돌아다닐 수 있을까?

 

 

입력

 

친구가 가진 의상의 수 n이 주어진다. ( 0<= n <= 30)

 

다음 n개에는 친구가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 

같은 종류의 의상은 하나만 입을 수 있다.

 

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

 

 

출력

 

각 테스트 케이스에 대해 친구가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력한다.

 

 

풀이

 

학창시절에 배웠던 옷을 입는 경우의 수를 떠올려보자.

 

상의 3개와 바지 2개가 존재할 때 옷을 입는 방법은 몇 가지인가? 

 

총 3 * 2인 6가지가 존재한다. 

 

이 문제는 이 개념과 비슷하다.

 

대신 해당 옷 종류를 안 입는 경우를 추가하고, 알몸인 상태를 제거하기만 하면 된다.

 

카테고리에 대한 경우의 수를 구하는데, 이는 곱 사건이다. 따라서 각 카테고리 별 입는 경우의 수와 해당 카테고리를 입지 않는 경우의 수를 구하고, 각 경우의 수를 곱하면 된다. 

 

그 이유 전체 아무것도 입지 않은 경우를 제거해 주면 친구가 옷을 입고 밖에 돌아다니는 일 수가 도출된다. 

 

#include <bits/stdc++.h>

using namespace std;


int tc, n;
string a,b;
int main()
{

    cin >> tc;
    
    while(tc--){
        map<string, int> _map;
        cin >> n;
        
        
        for(int i=0; i < n; i++){
            cin >> a >> b;
            _map[b]++;
        }
        
        long long ret = 1;
        for(auto a: _map){
          ret *= ((long long) a.second + 1);
        }
        
        ret--;
        
        cout << ret << '\n';
        
    }
    
    
    

    return 0;
}

 

경우의 수는 그 크기가 매우 커질 수 있어 long long type으로 처리하는 것이 좋다.

 

map을 순회하면서 1을 더하는 경우는 해당 카테고리를 입지 않는 경우를 더해주는 로직이다.

 

ret--는 전체 알몸인 경우의 수를 제외하는 로직이다.