[백준] 9375 with C++

문제설명

---

입출력 예제

---

개념

　의상의 종류의 개수에 따라 경우의 수를 계산하는 문제다. 의상의 종류와 개수를 매칭시킬 수 있으므로 map 자료구조를 이용하여 카운팅할 때 사용하면 된다. 여기서 조합(Combination)의 개념이 등장하는데, 서로 다른 n개의 원소를 순서에 상관없이 r개의 원소를 선택하는 것이다. 예를 들어 headgear, headgear, eyewear, face를 골랐으면 다음과 같이 계산하면 된다.

 

---

풀이

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

int main()
{
	int num;
	cin >> num;

　테스트 케이스의 개수를 num으로 초기화한다.

 

	while (num--)
	{
		map<string, int> _map;
		int n;
		cin >> n;

		int result = 1;

　문자열의 개수를 n으로 초기화하고, result를 1로 초기화해 준다.

 

		for (int i = 0; i < n; i++)
		{
			string name;
			string cloths;
			cin >> name >> cloths;
			_map[cloths]++;
		}

　이름과 옷의 종류를 입력받고, 종류의 개수를 늘려준다.

 

		for (auto& c : _map)
			result *= (c.second + 1);
		
		cout << result - 1 << '\n';
	}
}

　입력이 끝났으면, 맵에 있는 자료를 하나씩 꺼내며 연산을 해준다. 마지막 결과를 출력할 때 1을 빼줘야 하는데, 옷을 하나도 입지 않는 날이 포함되어 있기 때문이다.

 

총합본

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

int main()
{
	int num;
	cin >> num;

	while (num--)
	{
		map<string, int> _map;
		int n;
		cin >> n;

		int result = 1;

		for (int i = 0; i < n; i++)
		{
			string name;
			string cloths;
			cin >> name >> cloths;
			_map[cloths]++;
		}

		for (auto& c : _map)
			result *= (c.second + 1);
		
		cout << result - 1 << '\n';
	}
}