[Algorithm] Baekjoon 9375번 : 패션왕 신해빈

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

9375번: 패션왕 신해빈

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 0;
    int costumes = 0;
    string is1 = "";
    string is2 = "";
    vector<int> results;
 
    cin >> t;
 
    for (int i = 0; i < t; i++)
    {
        cin >> costumes;
        int sum = 1;
        map<string, int> m;
 
        for (int j = 0; j < costumes; j++)
        {
            cin >> is1 >> is2;
            m[is2]++;
        }
 
        for (auto iter = m.begin(); iter != m.end(); ++iter)
        {
            sum *= iter->second + 1;
        }
 
        results.push_back(sum-1);
 
    }
 
    for (int i = 0; i < results.size(); i++)
    {
        cout << results[i] << endl;
    }
 
}

프로그래머스에서 '위장'이라는 문제로 동일한 문제가 있다.

조합의 수를 구하는 문제이다.

여러부위에 대해 옷들이 주어지는데, 중요한것은 '단 한개라도' 착용하고 있으면 된다는 점이다.

 

만약 모자 2개, 상의 1개가 주어졌다고 가정하자.

여기서 2*1을 해서 나오는 2라는 값은, 반드시 모자와 상의를 1개씩 착용해야한다는 전제하에 나오는 경우의 수이다.

근데 이 문제에서는 그럴필요가 없다. 그냥 어떤종류의 옷이 몇개가 주어지든, 아무거나 1개라도 입고있으면 된다.

그렇기때문에 각 종류에 '착용안함'이라는 선택지를 하나씩 더준다.

그러면 2*1이 아니라 (2+1) * (1+1) = 6    이라는 결과가 나온다. +1이 착용안함이라는 선택지이다.

여기서 끝이 아니라, 하나라도 착용해야하기 때문에 '모든 부위에 착용안함'이라는 경우의수 한가지를 빼줘야한다.

그러면 6 - 1 => 5가 나오며 이게 정답이다.