[백준] 9375 패션왕 신해빈

✔️ 문제 링크

 

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

9375번: 패션왕 신해빈

---

✔️ 문제 이해

1. N개의 의상과 그 종류가 주어진다.

2. 이 때 알몸이 아닌 상태로 의상을 입을 수 있는 경우의 수를 출력해야한다. 

---

✔️ 설계

1. 입력이 위와 같이 들어온다. map을 사용하여 의상 정보를 저장했다.  map<의상개수, 의상종류>

2. 이 때 알몸이 아닌 상태로 의상을 입을 수 있는 모든 경우의 수는 각 의상의 개수에 +1을 하여 서로 곱해주고 -1을 하면 된다. (의상1 개수 + 1) x (의상2 개수  +1)  x (의상3 개수 +1 ) x .... x (의상n 개수 +1 ) - 1

3. 각 의상 개수에 +1을 해주는 이유는 해당 의상을 입지 않았을 경우를 고려하기 위함이고, 마지막에 -1을 하는 이유는 모든 의상을 입지 않을 경우를 하나 빼주기 위함이다. 

---

✔️ 문제 회고

1. map을 사용하여 아주 간단히 풀었다.

2. 경우의 수를 계산하는 수학적 사고력이 필요했던 것 같다. 

3. iterator로 컨테이너에 접근하는 것이 약간 어색했다. 더 익숙해지자.

---

👨🏻‍💻 소스 코드

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

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

	int t;
	cin >> t;

	while (t--) {
		map<string, int> clothMap;
		int n;
		cin >> n;
		int res = 1;

		while (n--) {
			string name, kind;
			cin >> name >> kind;
			clothMap[kind]++;
		}
		
		for (map<string, int>::iterator it = clothMap.begin(); it != clothMap.end(); it++) {
			res *= it->second+1;
		}

		cout << res -1 << endl;

	}
}