백준 9375번 [패션왕 신해빈](C++) -yes6686- 티스토리

백준 문제 풀이: 9375 [패션왕 신해빈]

---

문제 링크: https://www.acmicpc.net/problem/9375

문제 설명:

신해빈은 하루에 최소 한 개의 의상을 입어야 합니다. 다양한 종류의 의상이 주어질 때, 서로 다른 의상 조합의 수를 계산하세요.

입력 조건:

• 첫 번째 줄에 테스트 케이스의 개수 T가 주어집니다. (1 ≤ T ≤ 100)
• 각 테스트 케이스의 첫 줄에 의상의 수 n이 주어집니다. (0 ≤ n ≤ 30)
• 다음 n개의 줄에는 의상의 이름과 종류가 주어집니다. 이름은 중복될 수 있지만 종류는 고유합니다.

출력 조건:

• 각 테스트 케이스에 대해 서로 다른 의상 조합의 수를 출력합니다.

---

문제 해결 코드

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        map<string, int> m; // 종류별 의상 개수 저장
        string item, category;

        for (int i = 0; i < n; i++) {
            cin >> item >> category;
            m[category]++;
        }

        int result = 1;
        for (auto& pair : m) {
            result *= (pair.second + 1); // (해당 종류 의상 수 + 1) 곱하기
        }

        cout << result - 1 << '\n'; // 모두 안 입는 경우 제외
    }

    return 0;
}

---

코드 설명

위 코드는 조합론을 사용하여 의상 조합 수를 계산합니다.

• 입력 처리:
  • 각 의상의 종류별로 `map`에 저장하여 개수를 관리합니다.
• 조합 계산:
  • 각 종류별로 (의상 수 + 1)을 곱합니다. 여기서 `+1`은 해당 종류의 의상을 입지 않는 경우를 포함합니다.
• 최종 결과:
  • 모든 종류의 의상을 입지 않는 경우를 제외하기 위해 결과에서 1을 뺍니다.

시간 복잡도 분석:

• 입력 처리: O(n).
• 조합 계산: O(k), k는 의상의 종류 수.
• 전체 시간 복잡도: O(T × (n + k)).

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
2
3
hat headgear
sunglasses eyewear
turban headgear
3
mask face
sunglasses face
makeup face

출력:
5
3

첫 번째 테스트 케이스에서 5가지 의상 조합이 가능하며, 두 번째 테스트 케이스에서는 3가지 조합이 가능합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!