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

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

9375번: 패션왕 신해빈

소스 코드 :

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

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	
	while (n != 0)
	{
		string name;
		string cloth;
		int num;
		int result = 1;
		cin >> num;
		map<string, int> category;

		for (int i = 0; i < num; i++)
		{
			cin >> name >> cloth;

			if (category.find(cloth) != category.end())
			{
				category[cloth]++;
			}

			else
			{
				category.insert({ cloth,1 });
			}

		}

		for (auto iter = category.begin(); iter != category.end(); iter++)
		{
			result *= (iter->second) + 1;
		}

		result--;
		cout << result << '\n';

		n--;
	}
}

마무리 : 계산 문제인 것을 확인하여 dp로 풀 수 있나 확인했지만 그것은 아니였다.

 그러면 직접 계산해야하는 방법 밖에 없어 보였는데 종류의 개수마다 for문을 쓰기에는 종류가 다양할 수 있어서 채택하지 않았다. 그래서 임의로 계산을 한 결과 종류마다 곱해주고 1만 빼주면 답이 나온다는 것을 알 수 있었다.