[백준] 9375번: 패션왕 신해빈 [C++]

 

알고리즘 분류: 수학, 자료 구조, 조합론, 해시를 사용한 집합과 맵

문제 링크: https://www.acmicpc.net/problem/9375

9375번: 패션왕 신해빈

 

 

 

 

【 풀이 】

 

조합에 대한 수학적 사고력과 이를 해시맵으로 해결하는 능력을 묻는 문제이다.

조합(Combination)에 대해서 깊게 생각해 봤지만, 간단한 아이디어 하나로 풀 수 있는 문제였다.

 

같은 종류의 의상을 2개 이상 입으면 안된다고 하였기 때문에 결국 각 의상 종류에서는 하나만 입을 수 있게 되는 것이다.

즉 각 의상 종류마다 옷을 하나씩 입는 경우와 그 종류 옷을 아예 입지않는 경우(+1)를 의상 종류마다 곱해주면 그것이 경우의 수가 된다.

따라서 (의상 종류 +1) * (의상 종류+1) *...  -1 이 식이 된다.

마지막에 -1을 해주는 것은 옷을 아예 입지 않는 경우는 빼야 하기 때문이다.

 

 

 

【 코드 】

 

#include<iostream>
#include<map>
#include<string>
using namespace std;

int main(void)
{
	int t;
	cin >> t;

	for (int i = 0; i < t; i++)
	{
		int result = 1;
		int n;
		map<string, int>fashion;		//	사실상 key(의상종류)만 필요로 하게 된다.
		cin >> n;

		for (int j = 0; j < n; j++)
		{
			string s1,s2;
			cin >> s1>>s2;
			if (fashion.find(s2) != fashion.end())
				fashion[s2]++;
			else
				fashion[s2] = 1;
		}

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