백준 s3 9375 패션왕 신해빈 c++

https://www.acmicpc.net/problem/9375

9375번: 패션왕 신해빈

 

문제

T개의 테스트 케이스가 주어진다.

N개의 "물건 이름, 물건 종류"가 주어진다. 한 물건 종류에는 하나의 물건 밖에 착용할 수 없을 때, 해빈이가 입을 수 있는 옷 종류의 가짓수는?

 

풀이

string을 index로 할 수 있는 unordered_map을 사용해서 각 물건의 가짓수를 cnt한다.

한 물건 종류마다 입을 수 있는 경우의 수 (cnt) + 안 입는 경우 (1) 을 곱해준다.

모두 곱한 후에 나온 결과물에서 아무것도 입지 않은 경우의 수 1을 빼준다.

 

STL unordered_map

• map.clear()로 초기화 가능
• pair형태로 저장되어 있음.
  • ex. for (auto: a: map)
               cout << a.first << a.second << "\n";

 

전체 코드

/*boj s3 9375 패션왕 신해빈*/
#include <iostream>
#include <unordered_map>
#define MAXN 32
using namespace std;

int T, N;
unordered_map<string, int> cnt;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--) {
        cnt.clear();
        cin >> N;
        for (int i = 0; i < N; i++) {
            string name, type;
            cin >> name >> type;

            if (cnt.count(type) == 0)
                cnt[type] = 1;
            else
                cnt[type]++;
        }
        int ans = 1;
        for (auto a : cnt) {
            ans *= (a.second + 1);
        }
        cout << ans - 1 << "\n";
    }
}