#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
int solution(vector<vector<string>> clothes)
{
int answer = 1;
unordered_map<string, int> m;
for (const auto& cloth : clothes)
m[cloth[1]]++;
for (auto &pair : m)
answer *= (pair.second + 1);
return answer - 1;
}복잡하게 하지 않고 쉽게 푸는 방법이 무엇이 있을까 고민 중 이산수학을 배울 때 쓰던 조합 공식을 써야하는 줄 알았다.
머리를 싸매다가 찾아보니 간단한 공식이 있었다.
옷들의 조합을 구하는 공식은 확률론 및 조합론의 기본 원리에 따른 것이다. 이 공식은 "별개의 사건 중 하나를 선택하는 방법"을 표현하기 위한 것이다.
모든 조합 경우 의 수 = (A + 1) (B + 1) (C + 1) - 1(입지 않는 것)
위의 공식을 사용하면 어렵지 않게 풀 수 있다.
1을 빼주는 이유는 "하루에 최소 한 개의 옷을 입는다" 라는 말이 있기 때문이다.
입지 않는 경우를 포함하기 위해 각 항에 +1을 해주고, 모든 의상의 종류 중 아무것도 입지 않는 경우의 수를 한개 빼기 위하여 -1을 해주는 것이다.
그 공식을 보고 바로 unordered_map, 즉 해시를 사용하여 각 의상 종류에 몇 벌의 옷이 있는지 반복문을 한번 돌리고, 다시 한번 반복문을 돌려서 위의 공식을 이용해 Value의 값에 +1을 더한 값을 answer에 곱했다.
그 후 마지막으로 1을 뺀 값을 return하면 통과할 수 있었다.
다음부터 이런 옷들의 조합 문제가 나온다면 쉽게 풀 수 있겠다고 생각했다.
덤으로 수학을 열심히 했었더라면 찾아보지 않고 풀지 않았을까..
·ᴗ·