알고리즘 :: 백준 :: 9375 - 패션왕 신해빈

 

 

 

 

 

 

 

❔문제

🔗문제링크

 

🔄 문제 및 입출력 조건 파악

입력:

• 테스트케이스 T ≤ 100
• 의상 개수 ≤ 30
• 의상 한 종류는 하나만 입을 수 있음
• 중복 이름 없음, 모두 소문자로 구성

출력: 총 경우의 수

✏️ 문제풀이

 

'의상종류'칸에는 하나의 '의상'만 들어갈 수 있습니다.

'안 입는다, 안 쓴다' 라는 선택지를 포함하면 위 그림과 같습니다.

중요한 것은 '의상종류'와 그 종류에 포함된 의상의 개수입니다. 또한, 의상은 중복해서 입력되지 않습니다.

따라서 문자열 '의상종류'와 이에 포함된 의상 개수를 카운트 하기 위해 `std::map<std::string, int>`를 사용하는 것이 적절하겠습니다.

📝 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
    int T;
	cin >> T;
    
	while (T--) {
		int N;
		cin >> N;
        
		unordered_map<string, int> dict;
		dict.reserve(N);
        
		while (N--) {
			string name, type;
			cin >> name >> type;
			dict[type] += 1;
		}
		int ret = 1;
		for (auto i : dict) ret *= (i.second + 1);
		cout << ret - 1 << '\n';
	}
}

 

가장 마지막에 `ret - 1`로 아무것도 안 입는 경우 한 가지를 빼주는 것에 주의합시다

 

🔗 코드 링크

🕧 결과