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

https://www.acmicpc.net/problem/9375

핵심 아이디어 및 정답 코드

- 해당 옷을 입지 않은 경우의 수를 같이 구하면 한번에 구할 수 있음

- 의상 종류 개수 + 1을 전부 곱하면, 아무것도 입지 않은 경우의 수가 포함되므로 마지막에 1을 빼줌

 + 처음에 DFS로 접근했다가 시간 초과를 경험함ㅠ;

 

정답 코드

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

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int totalCount;
	cin >> totalCount;

	for (int i = 0; i < totalCount; i++)
	{
		map<string, int> m;
		int count;
		cin >> count;

		for (int j = 0; j < count; j++)
		{
			string str;
			cin >> str;
			cin >> str;

			if (m.find(str) == m.end())
				m.insert({ str, 1 });
			else
				m[str]++;
		}

		int answer = 1;
		for (auto iter = m.begin(); iter != m.end(); iter++)
			answer *= (iter->second + 1);

		cout << answer - 1 << '\n';
	}

	return 0;
}