[class3] (백준 9375) 패션왕 신해빈

문제

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

입력

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

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

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

출력

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

제한

 

예제 입력 1

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

예제 출력 1

5
3

힌트

첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로   (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다.

W3sicHJvYmxlbV9pZCI6IjkzNzUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMjhcdWMxNThcdWM2NTUgXHVjMmUwXHVkNTc0XHViZTQ4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NzRcdWJlNDhcdWM3NzRcdWIyOTQgXHVkMzI4XHVjMTU4XHVjNWQwIFx1YjllNFx1YzZiMCBcdWJiZmNcdWFjMTBcdWQ1NzRcdWMxMWMgXHVkNTVjXHViYzg4IFx1Yzc4NVx1YzVjOFx1YjM1OCBcdWM2MzdcdWI0ZTRcdWM3NTggXHVjODcwXHVkNTY5XHVjNzQ0IFx1YzgwOFx1YjMwMCBcdWIyZTRcdWMyZGMgXHVjNzg1XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWM2MjRcdWIyOTggXHVkNTc0XHViZTQ4XHVjNzc0XHVhYzAwIFx1YzU0OFx1YWNiZCwgXHVjZjU0XHVkMmI4LCBcdWMwYzFcdWM3NTgsIFx1YzJlMFx1YmMxY1x1Yzc0NCBcdWM3ODVcdWM1YzhcdWIyZTRcdWJhNzQsIFx1YjJlNFx1Yzc0Y1x1YjBhMFx1Yzc0MCBcdWJjMTRcdWM5YzBcdWI5N2MgXHVjZDk0XHVhYzAwXHViODVjIFx1Yzc4NVx1YWM3MFx1YjA5OCBcdWM1NDhcdWFjYmRcdWIzMDBcdWMyZTAgXHViODBjXHVjOTg4XHViOTdjIFx1Y2MyOVx1YzZhOVx1ZDU1OFx1YWM3MFx1YjA5OCBcdWQ1NzRcdWM1N2NcdWQ1NWNcdWIyZTQuIFx1ZDU3NFx1YmU0OFx1Yzc3NFx1YWMwMCBcdWFjMDBcdWM5YzQgXHVjNzU4XHVjMGMxXHViNGU0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NFx1YjU0YyBcdWFjZmNcdWM1ZjAgXHVkNTc0XHViZTQ4XHVjNzc0XHViMjk0IFx1YzU0Y1x1YmFiOFx1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjMGMxXHVkMGRjXHViODVjIFx1YmE3MFx1Y2U2MFx1YjNkOVx1YzU0OCBcdWJjMTZcdWM1ZDAgXHViM2NjXHVjNTQ0XHViMmU0XHViMmQwIFx1YzIxOCBcdWM3ODhcdWM3NDRcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1Y2Q1Y1x1YjMwMCAxMDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NzRcdWJlNDhcdWM3NzRcdWFjMDAgXHVhYzAwXHVjOWM0IFx1Yzc1OFx1YzBjMVx1Yzc1OCBcdWMyMTggbigwICZsZTsgbiAmbGU7IDMwKVx1Yzc3NCZuYnNwO1x1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMmU0XHVjNzRjIG5cdWFjMWNcdWM1ZDBcdWIyOTQgXHVkNTc0XHViZTQ4XHVjNzc0XHVhYzAwIFx1YWMwMFx1YzljNCZuYnNwO1x1Yzc1OFx1YzBjMVx1Yzc1OCBcdWM3NzRcdWI5ODRcdWFjZmMgXHVjNzU4XHVjMGMxXHVjNzU4IFx1Yzg4NVx1Yjk1OFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWM3NThcdWMwYzFcdWM3NDAgXHVkNTU4XHViMDk4XHViOWNjIFx1Yzc4NVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgMVx1Yzc3NFx1YzBjMSAyMFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOFx1Yzc4OFx1YzczY1x1YmE3MCBcdWFjMTlcdWM3NDAgXHVjNzc0XHViOTg0XHVjNzQ0IFx1YWMwMFx1YzljNCBcdWM3NThcdWMwYzFcdWM3NDAgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVkNTc0XHViZTQ4XHVjNzc0XHVhYzAwIFx1YzU0Y1x1YmFiOFx1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjMGMxXHVkMGRjXHViODVjIFx1Yzc1OFx1YzBjMVx1Yzc0NCBcdWM3ODVcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgaGVhZGdlYXJcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1Yzc1OFx1YzBjMVx1Yzc3NCBoYXQsIHR1cmJhblx1Yzc3NFx1YmE3MCBleWV3ZWFyXHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWM3NThcdWMwYzFcdWM3NzQgc3VuZ2xhc3Nlc1x1Yzc3NFx1YmJjMFx1Yjg1YyAmbmJzcDsgKGhhdCksICh0dXJiYW4pLCAoc3VuZ2xhc3NlcyksIChoYXQsc3VuZ2xhc3NlcyksICh0dXJiYW4sc3VuZ2xhc3NlcylcdWI4NWMgXHVjZDFkIDVcdWFjMDBcdWM5YzAgXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiOTM3NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkluY29nbml0byIsImRlc2NyaXB0aW9uIjoiPHA+U3BpZXMgdXNlIGF0dHJpYnV0ZXMgdG8gZGlzZ3Vpc2UgdGhlbXNlbHZlcyB0byBtYWtlIHN1cmUgdGhhdCB0aGV5IGFyZSBub3QgcmVjb2duaXplZC4gRm9yIGV4YW1wbGUsIHdoZW4gcHV0dGluZyBvbiBzdW5nbGFzc2VzLCBhIHNweSBzdWRkZW5seSBsb29rcyBjb21wbGV0ZWx5IGRpZmZlcmVudCBhbmQgY2Fubm90IGJlIHJlY29nbml6ZWQgYW55bW9yZS4gRXZlcnkgY29tYmluYXRpb24gb2YgYXR0cmlidXRlcyBnaXZlcyBhIGRpZmZlcmVudCBhcHBlYXJhbmNlLCBidXQgbm90IGFsbCBjb21iaW5hdGlvbnMgYXJlIHBvc3NpYmxlLiBGb3IgZXhhbXBsZSwgYSBoYXQgYW5kIGEgdHVyYmFuIGFyZSBib3RoIGhlYWRnZWFyIGFuZCBjYW5ub3QgYmUgdXNlZCBhdCB0aGUgc2FtZSB0aW1lLiBHaXZlbiB0aGUgbGlzdCBvZiBhdmFpbGFibGUgYXR0cmlidXRlcywgY29tcHV0ZSBob3cgbWFueSBkaXN0aW5jdCBkaXNndWlzZXMgY2FuIGJlIG1hZGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgXHVmYjAxcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYW4gaW50ZWdlciBuICgwICZsZTsgbiAmbGU7IDMwKTogdGhlIG51bWJlciBvZiBhdmFpbGFibGUgYXR0cmlidXRlcy48XC9saT5cclxuXHQ8bGk+biBsaW5lcyB3aXRoIHR3byBzcGFjZS1zZXBhcmF0ZWQgc3RyaW5nczogdGhlIG5hbWUgYW5kIHRoZSBjYXRlZ29yeSBvZiB0aGUgYXR0cmlidXRlLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkFsbCBzdHJpbmdzIGNvbnNpc3Qgb2YgYXQgbGVhc3QgMSBhbmQgYXQgbW9zdCAyMCBsb3dlcmNhc2UgbGV0dGVycy4gV2l0aGluIGEgdGVzdCBjYXNlIGFsbCBuYW1lcyBhcmUgZGlzdGluY3QuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGFuIGludGVnZXI6IHRoZSBudW1iZXIgb2YgcG9zc2libGUgZGlzdGluY3QgZGlzZ3Vpc2VzIHRoYXQgY2FuIGJlIG1hZGUgd2l0aCB0aGUgZ2l2ZW4gYXR0cmlidXRlcywgc3VjaCB0aGF0IGF0IG1vc3Qgb25lIGF0dHJpYnV0ZSBmcm9tIGVhY2ggY2F0ZWdvcnkgaXMgdXNlZC48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2013 I번

• 문제를 번역한 사람: lll4592
• 문제의 오타를 찾은 사람: sunsal0704

#include <iostream>
#include <map>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testCase, input, result=0;
    string temp;
    map<string, int> clothes;
    cin >> testCase;
    while (testCase-- > 0)
    {
        cin >> input;
        clothes.clear();
        result = 1;
        for (int i = 0; i < input; i++)
        {
            cin >> temp >> temp;
            if (clothes.find(temp) != clothes.end())
            {
                clothes[temp] += 1;
            }
            else
            {
                clothes[temp] = 1;
            }
        }

        for (auto i = clothes.begin(); i != clothes.end(); i++)
        {
            result *= (i->second+1);
        }
        cout << result-1 << '\n';
    }
    return 0;
}