문제 링크
https://www.acmicpc.net/problem/9375
시간, 공간 제한
시간 : 1초
공간 : 128 MB
문제 접근 방향
- 경우의 수 문제라고 생각하고 접근을 하였는데 같은 카테고리에 몇개가 들어 있는지만 중요하다는 생각을 하였음.
- key value 자료 구조 필요하다고 생각함 map<string, int>
- 조합을 통해 문제를 해결하려고 생각하였는데 막혔음.
- 아무것도 입지 않았을 때를 경우에 수에 추가를 하면 쉽게 풀 수 있다는 것을 풀이를 보고 알게됨
- 모든 경우의 수에서 아무 것도 입지 않았을 때 경우의 수 1을 빼주면 답이됨
#include <iostream>
#include <map>
using namespace std;
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
map<string, int> m;
for (int i = 0; i < n; ++i)
{
string a, b;
cin >> a >> b;
++m[b];
}
long ret = 1;
for (auto a : m)
ret *= (a.second + 1);
cout << ret - 1 << '\n';
}
return (0);
}
배운점
- 경우의수 문제일 때 아무 것도 하지 않는 것에 대한 경우도 같이 생각해보면 문제가 쉽게 풀릴 수 있다.
'PS > BOJ' 카테고리의 다른 글
BOJ 6064 카잉 달력 (0) | 2023.02.08 |
---|---|
BOJ - 9996 (0) | 2023.02.01 |
BOJ - 2309 일곱난쟁이 (0) | 2023.01.18 |