백준 9375 패션왕 신해빈(C++)

* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다

백준 9375 패션왕 신해빈 입니다

 

문제 해석

패션왕 신해빈 문제해석 입니다

우선 이문제같은경우는 경우의수를 찾는 문제입니다 즉 각 의상 종류에따른 어떤 의상을 조합해서 입을수있는지에 대한 경우의수를 파악하는 문제입니다

 

첫번째 예제같은경우는 다음과 같이 입력이 들어와있습니다

[hat,headger],[sunglassess,eyewear],[turban,headgear]

이렇게 입력이 들어와있을때 같은 종류의 의상은 하나만 입을수있다는 조건과, 아예 안입는 조건은 없다고 했으니 아래와 같이 5가지의 경우의 수가 만들어지게됩니다

(hat),(turban),(sunglassess),(hat,sunglasses),(turban,sunglasses)

 

이 예제로 볼수있는부분은 일단 의상의 이름 없이도 경우의수를 파악할수있습니다 즉, 의상의 종류로만으로도 경우의수가 파악이 가능합니다

 

그러면 의상의 종류로만 경우의수를 파악해보겠습니다

headger(hat)	headger(turban)	eyewear(sunglassess)
O	X	X
O	X	O
X	O	X
X	O	O
X	X	O
X	X	X

표를 보게 되면 각 의상의 종류마다 안입는 경우가 존재합니다

headger 만 입는경우 eyewear를 안입고, eyewear만 입는경우 headger를 안입어야 됩니다, 즉 각 의상의 종류에 안입는 다는 수가 한가지 늘어나게됩니다

headger(2개) + 안입는경우(1개) = 3

eyewar(1개) + 안입는경우(1개) = 2

여기서 나온 값은 곱해주면 3x2 = 6 이 나오게 되는데 이때 아예 아무것도 안입는 경우는 없으니 나온 결과에 -1을 해주게 되면 5가 나오게됩니다

 

문제 풀이 순서

1. 테스트 케이스 의 수, 의상수를 선언 합니다

2. 의상이름, 의상 종류를 입력받을 변수를 선언 합니다

3. 테스트 케이스를 입력받고, 테스트 케이스만큼 순회를 돕니다

4. <string,int> 로 구성된 맵을 선언해주고 의상의 수를 입력받습니다

5. 의상이름,의상 종류를 입력받고, 의상 종류를 키로하여 위에서 선언한 맵을 통하여 의상의 종류를 카운팅 합니다

6. 그리고 맵을 순회하면서 안입은경우 까지 생각하여 카운팅한 값에 +1을 해주고 최공 결과에 곱해줍니다

7. 최종결과가 나오면 아무것도 안입는경우를 빼줍니다

 

작성 코드

#include<bits/stdc++.h>
using namespace std;

//테스트케이스 수, 의상수 선언
int t,n;

//의상이름,의상 종류 변서 순언
string a,b;
int main(){

    //테스트 케이스 입력
    cin >> t;

    //테스트 케이스만큼 순회
    while(t--){
        
        map<string,int> mp1;
        
        //의상의 수 입력
        cin >> n;
        for(int i = 0; i < n; i++){
            //의상이름,의상 종류 입력
            cin >> a >> b;
            //선언한 맵에 의상종류 키에 해당하는 정수값을 +1(종류 카운팅)
            mp1[b]++;
        }
        long long ret = 1;
        //입력받은 맵을 순회
        for(auto c : mp1){
            //안입은 경우 까지 생각해서 카운팅한 숫자에 +1을 한후 곱하기
            ret *= ((long long)c.second + 1);
        }

        //아예 안입은 경우는 없다했으니 최종 결과에 -1
        ret--;
        cout << ret << "\n";
    }
    return 0;
}