백준 알고리즘 9375번: 패션왕 신해빈 [C++]

문제 출처: www.acmicpc.net/problem/9375

9375번: 패션왕 신해빈

1. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {
	int t;
	cin >> t;

	while (t--)
	{
		int n;
		cin >> n;
		string temp;
		vector <string> r(n);		//의상 종류 저장
		for (int i = 0; i < n; i++)
			cin >> temp >> r[i];

		vector <string> a(r);		//벡터 r 복사

		sort(r.begin(), r.end());	//오름차순으로 정렬 
		r.erase(unique(r.begin(), r.end()), r.end()); //중복 제거
		
		vector <int> q(n);
		for (int i = 0; i < r.size(); i++)	//의상 종류당 갯수 확인
			for (int j = 0; j < n; j++)
				if (r[i] == a[j])
					q[i]++;

		int sum = 1;
		for (int i = 0; i < r.size(); i++)	// (의상 종류당 갯수 + 해당 옷)
			sum *= (q[i] + 1);

		cout << sum - 1 << endl;		//알몸인 상태 제거
	}
}

(실행)

2. 풀이

int t;
cin >> t;

while (t--)

테스트 케이스 횟수 입력 후 테스트 케이스 횟수만큼 반복문을 실행시켜준다.

int n;
cin >> n;
string temp;
vector <string> r(n);		//의상 종류 저장
for (int i = 0; i < n; i++)
	cin >> temp >> r[i];

의상 종류의 갯수는 입력 후 string temp는 의상 이름 정보인데 문제를 읽어보면 의상 이름은 큰 영향이 없다. 그렇기에 그냥 입력을 받기만 해준다. vector r은 의상 종류의 갯수만큼 할당해주고 입력을 해준다.

vector <string> a(r);		//벡터 r 복사

벡터 r은 변하기 때문에 정보를 보존하기 위해 새로운 벡터인 a에 벡터 r을 복사한다.

sort(r.begin(), r.end());	//오름차순으로 정렬 
r.erase(unique(r.begin(), r.end()), r.end()); //중복 제거

벡터 r에 저장된 요소들 중 중복된 값들을 제거해준다.

vector <int> q(n);
for (int i = 0; i < r.size(); i++)	//의상 종류당 갯수 확인
	for (int j = 0; j < n; j++)
		if (r[i] == a[j])
			q[i]++;

벡터 q는 의상 종류당 갯수를 저장해주는 벡터이다. 반복문을 통해 의상 종류 당 갯수를 확인해준다.

int sum = 1;
for (int i = 0; i < r.size(); i++)	// (의상 종류당 갯수 + 해당 옷)
	sum *= (q[i] + 1);
 
cout << sum - 1 << endl;			//알몸인 상태 제거

해당 식은 (옷 종류당 갯수 + 해당 옷 종류) * (옷 종류당 갯수 + 해당 옷 종류) ..... - 1이다. 이렇게 되면 원하는 결과를 얻을 수 있다. 반복적으로 곱해지는 것은 반복문을 통해 해결한 뒤 마지막에 1을 빼준다. 그러면 문제는 해결될 것이다.

3. 느낀 점

문제 풀이 내용 중 마지막에 쓰여있는 식을 도출할 수 있다면 쉽게 해결할 수 있을 것이다.