백준 9375/c++ )) 패션왕 신해빈

조합을 사용하여 입을 수 있는 의상의 경우의 수를 구하는 문제이다

의상 하나를 입력 시 의상의 이름 + " " + 의상의 종류 로 입력이 되기 때문에 공백을 전 후로 입력을 두번 받는셈이다

입력은 두개지만 의상의 이름은 필요없으므로 의상의 종류만으로 경우의 수에 고려한다

그 의상을 착용하지 않은 경우도 그 의상의 종류 중 하나로 더하여 계산한다

map을 통해 의상의 종류를 key값으로, 종류별 개수를 value값으로 저장하고

종류별 착용가능 개수를 모두 곱해서 (가지고 있는 종류+1미착용) 경우의 수를 구한다

그 중 모든 종류를 미착용한 알몸상태는 제외하니 -1 을 하여 최종 경우의 수를 구한다

그것을 테스트 케이스만큼 반복하는 문제이다

 

주의사항

map을 대입시 auto 자료형을 사용해야 된다

종류개수에 미착용시 개수도 +1 해서 곱해줘야 하며 알몸상태도 -1하여 빼주자

종류당 한가지만 선택할 수 있기에 종류당 조합은 상관없으므로 이름 입력은 사용하지 않는다

 

#include <bits/stdc++.h>
using namespace std;
int n, cn;
string a, b;

int main(){
	 
	 //테스트 케이스 수   
	cin >> n;
	// 의상 개수   
	for(int i=0; i<n; i++){
		// 의상 종류별 이름, 의상 개수 
		map<string, int> map1;
		// 경우의 수는 매우 커질 수 있으므로 형변환 해준다 
		long long ret=1;
		cin >> cn;
				
		// 옷 이름, 종류를 입력받아서 두번째 입력인 종류만 key로 가지고 그 수를 value로 ++카운팅 함  
		for(int j=0; j<cn; j++){
			cin >> a >> b;
			map1[b]++;
		}
		
		// map1을 모두 돌며 map.second+1(안입는 경우)의 값을 결과값 1에 곱함 
		// 벡터, map을 사용할경우 auto를 사용해서 동적으로 자료형에 대응한다  
		for(auto t : map1){
			// int 를 longlong으로 형변환 해준다  
			ret *=(long long)t.second+1;
		}
			// 알몸인 경우 1가지 제외 
		ret--;  	
		cout << ret << "\n";	
	}
	return 0;
}