BOJ 9375 패션왕 신해빈

문제 링크

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

시간, 공간 제한

시간 : 1초

공간 : 128 MB

문제 접근 방향

- 경우의 수 문제라고 생각하고 접근을 하였는데 같은 카테고리에 몇개가 들어 있는지만 중요하다는 생각을 하였음.

- key value 자료 구조 필요하다고 생각함 map<string, int>

- 조합을 통해 문제를 해결하려고 생각하였는데 막혔음.

- 아무것도 입지 않았을 때를 경우에 수에 추가를 하면 쉽게 풀 수 있다는 것을 풀이를 보고 알게됨

- 모든 경우의 수에서 아무 것도 입지 않았을 때 경우의 수 1을 빼주면 답이됨

#include <iostream>
#include <map>

using namespace std;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		map<string, int> m;
		for (int i = 0; i < n; ++i)
		{
			string a, b;
			cin >> a >> b;
			++m[b];
		}
		long ret = 1;
		for (auto a : m)
			ret *= (a.second + 1);
		cout << ret - 1 << '\n';
	}
	return (0);
}

배운점

- 경우의수 문제일 때 아무 것도 하지 않는 것에 대한 경우도 같이 생각해보면 문제가 쉽게 풀릴 수 있다.