패션왕 신해빈 (feat. 백준, 9375번)

패션왕 신해빈
https://www.acmicpc.net/problem/9375

9375번: 패션왕 신해빈

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/9375
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int T, N, ans, arr[31][31] = { 0 };
	string str1, str2;
	for (register int i = 1; i <= 30; ++i)
		arr[i][0] = arr[i][i] = 1;
	for (register int i = 2, j; i <= 30; ++i)
		for (j = 1; j < i; ++j)
			arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
	cin >> T;
	for (register int t = 0, i, ans; t < T; ++t) {
		cin >> N;
		map<string, int> tmp;
		for (i = 0, ans = 1; i < N; ++i) {
			cin >> str1 >> str2, ++tmp[str2];
		}
		for (auto& item : tmp)
			ans *= (arr[item.second][1] + 1);
		ans -= 1;
		cout << ans << "\n";
	}
	return 0;
}
// *&)*@*

1. 문제에서 요구하듯이 알몸은 안됩니다.
2. 그렇다면 3종류의 옷이 있다면 1종류 또는 2종류 또는 3종류 를 입을 수 있습니다.
3. 따라서 (A종류 중 1개 + 1) * (B종류 중 1개 + 1) * (C종류 중 1개 + 1) * ... - 1 이라는 점화식이 성립됩니다.
4. 괄호마다 +1을 하는 이유는 해당 종류 (A, B, C 등) 를 입어도 되고 안입어도 되기 때문입니다.
5. 마지막 -1을 하는 이유는 모든 의상을 착용했을 경우에 대해서 고려해야 하기 때문입니다.
6. 따라서 의상의 종류만을 가지고 어떤 종류가 있고 각 종류에는 몇개의 의상이 있는지만 보관한 뒤 연산하면 되겠습니다.