BAPC 2013 I번 incognito- 변장 > 문제은행 : 정보올림피아드&알고리즘



3699 : 변장

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
98 회   
시도횟수
170 회   

문제

정올이는 스파이 이다. 

변장술의 달인으로 이전과 같은 조합의 의상을 입고 밖을 나가지 않는다.

어제 안경, 코트, 신발을 입었다면 오늘은 안경대신에 썬그라스를 쓰거나

바지를 추가로 입거나 한다.

 

정올이가 가진 의상(장신구포함)​에 대한 정보를 입력받아

정올이가 적어도 하나 이상의 의상(장신구포함)​을 갖춘 상태로 

밖을 나갈 수 있는 날은 며칠이나 될까?

 

예를 들어 3개의 의상이 아래와 같이 주어졌다고 하자.

 

hat headgear

sunglasses eyewear

turban headgear​ 

 

이 경우 ​headgear​에 해당하는 의상이 hat, turban이고 

eyewear​에 해당하는 의상이 sunglasses​ 이므로 다음 5가지 조합이 가능하다.

(hat), (turban), (sunglasses), (hat, sunglasses), (turban, sunglasses)

 

 


입력형식

첫 행에 테스트 케이스 TC( 1 <= TC <= 100)가 입력된다.

각 테스트 케이스의 첫 행에는 정올이가 가진 의상의 수 N( 0 <= N <= 30)이 입력된다.

다음 N개의 행에 의상 이름과 의상 부류 이름이 문자열로 주어진다.

문자열의 길이는 1 ~ 20 이다. 의상 이름은 유일하다.

 

 


출력형식

각 테스트 케이스에 대하여 정올이가 밖에 나갈 수 있는 최대일수를 출력한다.


입력 예

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

출력 예

5
3

Hint!

1
2
3
4
5
6
[ 문자열 비교 함수]
 
int strcmp(const char*s, const char*t){
    while(*&& *== *t) ++s, ++t;
    return *- *t;
}​




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP