[백준] 9375.cpp : 패션왕 신해빈

www.acmicpc.net/problem/9375

9375번: 패션왕 신해빈

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

int main(void)
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    
    int tc;
    cin >> tc;
    for(int t = 0 ; t < tc ; t++)
    {
        int n;
        cin >> n;
        // 보기 편하게 의상의 종류들 모아놓은 벡터
        vector<string> cates;
        // 의상 종류별로 옷들 넣어놓는 맵, 옷 이름 대신 번호로 저장
        map<string, vector<int>> m;
        string cate;
        string cloth;
        for(int i = 0 ; i < n ; i++)
        {
            cin >> cloth >> cate;
            // 만약 처음 들어온 의상 종류라면
            if(m.find(cate) == m.end())
            {
                vector<int> clothes;
                // 의상 종류를 맵에 추가
                m.insert(pair<string,vector<int>>(cate, clothes));
                cates.push_back(cate);
            }
            // 해당 종류에 번호로 추가
            m[cate].push_back(m[cate].size() + 1);
        }

        int mul = 1;
        // (n + 1) * (m + 1) * ... * (x + 1) - 1
        for(int i = 0 ; i < cates.size() ; i++)
        {
            mul *= m[cates[i]].size() + 1;
        }
        cout << mul - 1<< '\n';
    }
}

 

[Approach]

1. <종류, 의상이름들> 의 맵을 만들어서 각각의 조합을 구해보기.

     -> 입었을 때의 경우의 수, 입지 않았을 때의 경우의 수에 대한 조합을 어떻게 다 구하지...?

     -> 조합으로 푸는 것이 아니라, 규칙을 찾아야 할 듯

 

[Point]

1. 간단하게 생각해서, 입지 않았을 때의 경우까지 고려해서 서로 곱해주면 된다. 다만 모두 안입은 경우의 수 하나는 빼줄 것

2. 맵도 벡터로 하나하나 다 넣어서 사이즈를 구할 필요 없이 전체 옷의 수만 업데이트해주는게 훨씬 좋을 듯.

3. 맵에 insert 따로 해줄 필요 없이 map[key] 해서 없을 경우 자동으로 만들어서 넣어준다는 점 알고 있을 것

4. 전체적으로 풀이가 너무 비효율적이다...ㅋㅋ

 

[More]

1. auto& 활용 + 반복자 사용