[알고리즘문제] 백준 패션왕 신해빈(9375번)

www.acmicpc.net/problem/9375

9375번: 패션왕 신해빈

해빈이가 옷을 입을 경우의 수를 계산하는 문제다.

각 의상별로 입거나 안입을 수 있으며 하나도 안입는 경우는 안된다.

의상의 이름은 겹치지 않는다.

의상의 종류는 겹쳐도 된다.

모든 경우의 수를 조합하여 return시킨다.

input

테스트케이스

의상수

의상이름 의상종류

output

경우의 수

#include<iostream>
#include<map>

using namespace std;

int solution(map<string, string> m) {
	map<string, int> tCase;
	for (map<string, string>::iterator it = m.begin(); it != m.end(); it++) {
		if (tCase.find(it->second) != tCase.end()) {
			tCase.find(it->second)->second  += 1;
		}
		else {
			tCase.insert(pair<string, int>(it->second, 1));
		}
	}

	int answer = 1;
	for (map<string, int>::iterator it = tCase.begin(); it != tCase.end(); it++) {
		answer *= (it->second + 1);
	}
	answer--;
	return answer;
}

int main() {
	int testCase = 0;
	int cnt = 0;
	string category, clothName;
	map<string, string> m;

	cin >> testCase;
	for (int i = 0; i < testCase; i++) {
		cin >> cnt;
		for (int j = 0; j < cnt; j++) {
			cin >> clothName >> category;
			m.insert(pair<string, string>(clothName, category));
		}
		cout << solution(m) << "\n";
		m.clear();
	}

	return 0;
}

1. 의상의 종류별로 몇개씩 있는지 확인한다.

2. 각 종류에 대한 경우의 수를 구하기 위해 의상의 종류의 갯수+1(+1 하는 이유는 안입는 경우도 계산하기 위해)을 곱한다.

3. 하나도 안입는 경우는 안되니 모든 경우의 수에서 하나를 뺀다.

4. 원하는 모든 경우의 수가 나왔으니 return하여 출력한다