[Algorithm] BOJ : 패션왕 신해빈

안녕하세요, iOS 개발하는 루피입니다.

 

오늘은 백준 9375번 패션왕 신해빈 문제를 풀어보겠습니다.

 

바로 시작합니다.

---

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

풀이

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

int main() {
    int testCase; cin >> testCase;
    for (int i=0;i<testCase;i++) {
        int num; cin >> num;
        map<string,int>m;

        for (int j=0;j<num;j++) {
            string name,type; cin >> name >> type;
            m[type]++;
        }
        int res = 1;
        // 핵심 로직
        for(auto it : m) res *= (it.second+1);
        cout << res-1 <<'\n';
    }
}

• 문제를 풀면 사실 상 name은 사용하지 않아도 됨을 인지할 수 있습니다.
• 핵심 로직 부분은 그림을 그려 설명해보겠습니다.

모자 1,2는 동그라미, 안경은 세모라고 가정해 봅시다. 

화살표를 따라가며 경우의 수를 체크할 수 있는데요.

• 안경을 쓰고 다른 조건을 선택할 경우 : 3 가지
• 안경을 안 쓰고 다른 조건을 선택할 경우 : 3가지
• 안경을 안쓰고 다른 조건도 선택하지 않을 경우 : 1가지
• 3 + 3 - 1 = 5가 됩니다.

 

이해가 가시나요? 다른 예시를 들어보겠습니다.

똑같이 모자 1,2,3는 동그라미, 안경 1,2은 세모라고 가정해 봅시다. 

화살표를 따라가며 경우의 수를 체크할 수 있는데요.

• 안경 1을 쓰고 다른 조건을 선택할 경우 : 4 가지
• 안경 2를 쓰고 다른 조건을 선택할 경우 : 4가지
• 안경을 안 쓰고 다른 조건도 선택할 경우 : 4가지
• 안경을 쓰지 않고 다른 조건도 선택하지 않을 경우 : 1가지
• 4+ 4 +4 - 1 = 11가 됩니다.

이해가 가시나요? 그렇 다면 하나 더 유추 할 수 있겠죠??

가능한 경우의 수는 : (타입의 개수 + 1) X (타입의 갯수 + 1) -1 = 전체 경우의 수라는 것입니다!

---

오늘도 화이팅입니다!