[백준 9375] 패션왕 신해빈

문제설명

 

첫줄에 테스트 케이스가 주어진다

그리고 그 다음, 옷의 수가 입력되고, 그만큼 옷이 입력된다

의상의 이름과 종류가 공백을 기준으로 구분되어 입력된다

같은 종류의 의상은 하나만 입을 수 있는데, 아무것도 입지 않은 상태로 총 며칠을 지낼 수 있는지 출력시킨다

알고리즘

1. 테스트 케이스, 옷의 수를 입력 받는다

2. 옷의 수 만큼 반복하여 옷의 종류와 이름을 입력 받는다

3. map을 사용하여 옷의 종류가 중복 되면 value 값을 증가 시키고, 중복되지 않은 경우 map에 넣는다

4. 식은 결국 각 옷의 종류+1을 해서 곱하면된다 그리고 아무것도 안입는 경우 1을 뺀다

코드

#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <map>
using namespace std;

int main() {
	int t,n; 
	cin >> t; 
	
	for (int i = 0; i < t; i++)
	{
		cin >> n;
		int answer = 1;
		map <string, int> clothes;
		for (int j = 0; j < n; j++)
		{
			string name, type;
			cin >> name>> type; 
			if (clothes.find(type) == clothes.end()) //없는 종류면 삽입
				clothes.insert({ type,1 });
			else//이미 있는 종류면 값 증가
				clothes[type]++;
		}  
		for (auto k: clothes){
			answer *= (k.second + 1);
		}
		cout << answer - 1 << '\n';
	}
	
}

고찰

해당 알고리즘은 key, value 쌍으로 이루어진 STL map을 사용하였다

map의 특징은 key 값이 같으면 들어오지 않는다는 것(중복 key 값 불가)이다

이번문제는 오랜만에 풀어서 한번에 생각해내지 못해서 map에 대한 공부가 추가적으로 필요하다고 느꼈다 

옷의 종류가 같으면 즉, key 가 같으면 value 를 1 증가 시키는 것이 포인트이다

그리고 확률과 통계에서 배웠던,,? 경우의 수를 생각해서 종류별 옷의 갯수 +1 을 한다음 곱하고 아무것도 입지 않았을 경우 -1을 해주면 결과가 나온다