[C++] 백준 9375: 패션왕 신해빈

문제

[C++] 백준 9375: 패션왕 신해빈 SILVER 3
https://www.acmicpc.net/problem/9375

 

---

 

접근 방법

이 문제는 옷의 이름은 필요 없고, 종류(type)별로 몇 개 있는지만 알면 되는 경우의 수 문제다.

• 입력으로 (옷 이름, 옷 종류)가 들어오지만, 실제로 필요한 건 “종류별 개수”이기 때문에
  map<string, int>을 사용해서 아래와 같이 저장했다.
  • key : 옷의 종류
  • value: 그 종류에 속하는 옷의 개수
    
    
• 예를 들어, 아래와 같다면 각 종류별 선택지는 다음과 같다.
  • headgear 2개
  • eyewear 1개
    
    
  • headgear: (안 씀) + 2개 중 하나 = 3가지
  • eyewear: (안 씀) + 1개 중 하나 = 2가지

따라서, 전체 경우의 수는 3 * 2 = 6이 된다.

이를 일반화하면, 각 종류마다 (해당 종류 개수 + 1)을 모두 곱한 뒤, 마지막에 아무것도 안 입는 경우 1가지를 빼서 -1 해주면 된다.

(2 + 1) * (1 + 1) - 1 = 5

map<string, int> m;
for (int i = 0; i < n; i++) {
    string name, type;
    cin >> name >> type;
    m[type]++;              // 종류별 개수 카운트
}

int ret = 1;
for (auto& p : m)          // 각 종류마다 (개수 + 1)을 곱함
    ret *= (p.second + 1);

cout << ret - 1 << '\n';    // 아무것도 안 입는 경우 제외

 

구현 시 주의할 점

1. for (auto& p : m) 이 문장의 의미

• m은 map<string, int> 이고, range-based for문에서 p의 타입은 pair<const string, int>가 된다.
• auto& p
  • auto: 타입을 자동 추론
  • &: 참조로 받아서 복사 비용 줄이기
• 그래서 아래를 의미한다.
  • p.first → 옷 종류 (key)
  • p.second → 그 종류의 개수 (value)

이번 문제에선 key는 필요 없고, p.second만 사용해서 (p.second + 1)을 곱해준다.

 

2. 경우의 수에서 +1과 -1의 의미

• +1 :
  각 종류마다 “아예 안 입는 선택지”를 하나 더해주는 것
• 마지막 -1 :
  모든 종류에서 “안 입는 것”만 고른, 즉 전부 안 입는 경우를 빼주기 위함

 

---

 

코드

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

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

    int test_case = 0;
    cin >> test_case;
    for (int t = 0; t < test_case; t++)
    {
        int n = 0;
        cin >> n;

        map<string, int> m;
        for (int i = 0; i < n; i++)
        {
            string name, type;
            cin >> name >> type;

            m[type]++;
        }

        int ret = 1;
        for (auto& p : m)
            ret *= (p.second + 1);

        cout << ret - 1 << '\n';
    }

    return 0;
}