[프로그래머스] 의상

옷의 이름과 종류가 담긴 배열이 주어졌을 때, 가능한 조합의 수를 구하는 문제.

처음에는 백트래킹으로 접근했었는데 모든 옷이 다른 종류일 경우 시간복잡도가 $O(2$30$)$이 되어버려서 TLE가 나왔다.

가짓수만 구하는 경우는 굳이 백트래킹할 필요 없이 각 옷의 종류별 개수에 '미착용'이라는 선택지를 더해 모두 곱하면 해결된다.

https://school.programmers.co.kr/learn/courses/30/lessons/42578

cpp code

#include <string>
#include <vector>
#include <map>

using namespace std;

map<string, int> M;

int solution(vector<vector<string>> clothes) {
    for (vector<string> v : clothes) {
        M[v[1]]++;
    }
    
    int ans = 1;
    for (pair<string, int> p : M) {
        ans *= p.second + 1;
    }
    
    return ans - 1;
}