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

옷을 입을 수 있는 경우의 수를 구하는 문제입니다.

같은 부위의 옷은 하나만 입거나 벗을 수 있고, 전부다 벗을 수는 없습니다.

입력받은 부위를 벡터에 저장하고 개수를 입력해주었습니다.
그리고 입력받은 개수를 통해서 부위별 옷의 개수를 세서 경우의 수를 구했습니다.
(x의 개수 + 1) * (y의 개수 + 1) * .... (n의 개수 + 1) - 1
+1은 벗은 경우이며, 마지막 -1은 전부 벗은 경우를 제외한 것입니다.

 

#include <iostream>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main(int argc, char *argv[])
{
	int ts;
	int n;
	int result;
	int flag;
	string s;
	vector<pair<string, int>> v;

	cin >> ts;

	while (ts--) {
		v.clear();
		flag = 0;
		result = 1;
		cin >> n;
		for (int i = 0; i < n; ++i) {
			cin >> s;
			cin >> s;
			pair<string, int> p;
			for (int i = 0; i < v.size(); ++i) {
				if (v[i].first == s) {
					++v[i].second;
					flag = 1;
					break;
				}
			}
			if (flag == 0) {
				p.first = s;
				p.second = 1;
				v.push_back(p);
			}
			flag = 0;
		}
		for (int i = 0; i < v.size(); ++i) {
			result *= v[i].second + 1;
		}
		result -= 1;

		cout << result << endl;
	}

	return 0;
}