[백준 C++] 9375 패션왕 신해빈 - 조합론

9375번: 패션왕 신해빈

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

unordered_map<string, int> Closet;

void TestCase()
{
	Closet.clear();

	int N;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		string First, Second;
		cin >> First >> Second;
		++Closet[Second];
	}

	int Case = 1;
	for (const pair<string, int>& Clothes : Closet)
	{
		Case *= (Clothes.second + 1);
	}
	cout << Case - 1 << '\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int T;
	cin >> T;
	for (int i = 0; i < T; ++i)
	{
		TestCase();
	}
}

---

 

해시맵을 이용해서 푸는 조합론 유형의 문제입니다.

풀이 과정은 다음과 같습니다.

 

1. unordered_map을 이용해서 각 옷의 종류 마다 옷의 개수를 저장

2. 각 옷 종류에서 옷의 개수 + 1(안 입는 경우) 중 한 개를 뽑는 경우의 수를 모두 곱하기

3. 최종 경우의 수 - 1(알몸인 경우)을 해주고 출력