[9375] 패션왕 신해빈

---

맨몸으로 갈 수 없으니 최소 1종류 이상의 의류를 착용해야 한다

 

M 종류의 옷이 3개일 때 우리가 옷을 고르는 경우의 수는

m1 선택, m2 선택, m3 선택, 아무것도 선택 x

총 4가지이다

결론은 M + 1가지의 경우의 수가 존재한다는 것이다

 

그렇게 의상의 종류만큼 반복하며 특정 종류의 옷 개수 + 1을 곱해야 한다

하지만 답은 1을 빼줘야 하는데, 이는 아무것도 입지 않은 경우의 수를 빼준 것이다

 

map을 이용하여 옷의 종류를 key로 하였다

조합론 문제이기 때문에 저번에 구현했던 이항 계수 코드를 가져와서 풀었다

그렇게 완성된 코드는 아래와 같다

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int T, N;

int dp[101][101];
int R;

int f(int n, int k) {

	for (int i = 0; i <= n; i++) {
		dp[i][0] = 1;
	}

	for (int i = 0; i <= k; i++) {
		dp[i][i] = 1;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]);
		}
	}

	return dp[n][k];
}

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

	f(100, 100); // 미리 조합 구해놓고 dp 배열에 할당하기

	cin >> T;
	for (int i = 0; i < T; i++)
	{
		cin >> N;

		// 초기화
		R = 1;
		unordered_map <string, int> mymap; 

		for (int j = 0; j < N; j++)
		{
			string wear, kind;
			cin >> wear >> kind;		
			// wear는 중복되지 않으므로 사실상 필요없음. 옷의 종류가 중요함
			// 1종류 이상은 무조건 착용해야 함
			// 
			// ex : M 종류의 옷이 3개일 때
			// m1선택,  m2선텍, m3선택, 아무것도 선택 x 
			// 총 (M + 1)가지의 경우의 수 존재

			mymap[kind]++; // 해당 종류의 옷 개수 증가
		}
		for (auto const& pair : mymap) {
			R *= dp[pair.second + 1][1]; // M+1C1 형태
		}
		printf("%d\n", R - 1); // 아무것도 입지 않은 경우를 빼줌
	}


}