문제

문제링크

해설

• 아이디어 하나가 떠오르지 않으면 한참을 해매는 전형적인 문제입니다.
• 예제입력의 첫 번째 테스트 케이스를 기준으로 설명해보겠습니다
  • 옷 종류는 headgear와 eyewear 두 가지 종류가 있고, headgear은 2가지, eyewear은 1가지 옷이 있습니다.
  • 옷의 이름은 중요하지 않고 옷의 종류만 중요하므로 옷의 종류별로 나열하면 다음과 같습니다.
    • Headgear: A1, A2
    • Eyewear: B1
  • 하지만, 숨겨진 경우의 수가 있는데 바로 ‘해당 옷 종류를 입지 않는 경우’입니다.
    • Headgear: A1, A2, X
    • Eyewear: B1, X
  • 위와 같이 생각한다면, 총 조합의 개수는 옷 종류 속 옷 개수의 곱이므로 3 x 2 = 6 입니다.
  • 그러나, {X, X} 조합은 불가능하므로 이 경우 한 가지를 제외하면 답은 5 입니다.
• 위와 같이 순열/조합 문제는 옷을 입지 않는 경우를 경우에 수에 포함해서 생각하는 아이디어를 생각하지 않으면, 한참을 어렵게 생각하게 되는 경우가 많습니다. 이번 기회에 조금 눈에 익혀둡시다.

코드

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        unordered_map<string, int> cloth;
        for (int i = 0; i < n; i++) {
            string name, type;
            cin >> name >> type;
            if (cloth.count(type)) cloth[type]++;
            else cloth.emplace(type, 1);
        }
        int answer = 1;
        // Combination can be calculated by multiplication every cloth type;
        for (const auto& it : cloth) answer *= (it.second + 1);
        answer -= 1;    // Check no cloth case.
        cout << answer << '\n';
    }
    return 0;
}

결과