반응형
<코드>
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int N, T;
int ans;
vector<pair<string, int>> v;
string s1, s2;
int main()
{
cin >> T; // 테스트케이스 수
while (T--)
{
ans = 1;
cin >> N; // 의상 수
for (int i = 0; i < N; i++)
{
cin >> s1 >> s2;
if (v.size() == 0) // 맨 처음 값 벡터에 저장 후 1개 체크
{
v.push_back(pair(s2, 1));
continue;
}
for (int j = 0; j < (int)v.size(); j++)
{
if (s2 == v[j].first)
{
v[j].second++; // 개수 체크
break;
}
if (j == (int)v.size() - 1) v.push_back(pair(s2, 0)); // vector에 있지않은 원소라면 추가.
}
}
for (int k = 0; k < (int)v.size(); k++) // 가능한 조합 수 구하기
ans *= (v[k].second + 1);
// 아무것도 안입는 경우인 1 빼기
cout << ans - 1 << "\n"; // 줄바꿈 꼭하기
v.clear(); // 벡터 비우기
}
}
최악의 경우는 의상이 30개에 모든 의상의 종류가 다를 경우이며 경우의 수는 2^30-1으로 int형의 범위를 넘어서지 않는다. 조합의 수는 만약 상의 x2, 하의 x2, 신발 x2 인 경우에는 (2+1)*(2+1)*(2+1) - 1 = 26이며 아무것도 안 입는 경우인 1을 빼주어야 한다. 출력할 때 줄 바꿈을 제대로 처리하지 않아 30분 정도 헤매었던 것 같다.
+위의 코드는 좀 복잡하게 풀이를 하였고 문제분류에 맞게 해시 맵을 이용하여 풀이해봤습니다. (2021.05.26 추가)
<2021-05-26 해시맵을 이용한 풀이 추가>
#include<iostream>
#include<map>
#include<string>
using namespace std;
int N, T;
int ans;
string s1, s2;
int main()
{
cin >> T; // 테스트케이스 수
while (T--)
{
map<string, int> m; // Map<의상종류,의상수>
ans = 1;
cin >> N; // 의상 수
for (int i = 0; i < N; i++)
{
cin >> s1 >> s2;
// 해당key값이 존재하지 않을 경우 find함수는 end()리턴
if (m.find(s2) == m.end())
{
m[s2] = 1;
}
else // 해당 key값이 존재할 경우
{
m[s2]++;
}
}
for (auto iter : m) // iter.first = key, iter.second = value
ans *= (iter.second + 1); // (의상수+1) 씩 곱하기
cout << ans - 1 << "\n";
}
}
문제에서 같은 이름을 가진 의상은 존재하지 않는다고 명시되어있기 때문에 의상 이름(s1)에 상관없이 의상 종류(s2)가 매핑되어있지 않다면 m[s2] = 1, 매핑되어있다면 m[s2]++을 하여 의상 종류별로 개수를 카운트하였습니다.
반응형
'🧩PS > 🥈Nomal' 카테고리의 다른 글
[C/C++] 백준 2004번 - 조합 0의 개수 (0) | 2020.12.06 |
---|---|
[C/C++] 백준 1676번 - 팩토리얼 0의 개수 (0) | 2020.12.06 |
[C/C++] 백준 11051번 - 이항 계수 2 (DP풀이) (0) | 2020.12.03 |
[C/C++] 백준 3036번 - 링 (0) | 2020.12.03 |
[C/C++] 백준 2609번 - 최대공약수와 최소공배수 (유클리드 호제법과 증명) (0) | 2020.12.02 |