조합론에서 곱 규칙은 여러 단계로 구성된 과정의 경우의 수를 세는 법칙이다. 어떤 과정이 k개의 단계로 구성되어있다고 하자. 첫째 단계의 경우의 수는 n1이며, 둘째 단계의 경우의 수는 n2...k째 단계의 경우의 수는 nk라고 하자. 곱 규칙에 따르면, 이들을 차례대로 거치는 과정의 경우의 수는 다음과 같다.
✅곱의 법칙으로 문제 해결 코드
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
int solution(vector<vector<string>> clothes)
{
int answer = 1;
unordered_map<string, int> clothes_cnt;
// clothes 2차원 vector를 map으로 변환
for (int i = 0; i < clothes.size(); ++i)
{
clothes_cnt[clothes[i][1]]++;
}
// map을 순회하며, 각 종류별 개수에서 입지 않은 경우 +1을 포함해서 누적 곱셈
for (const auto& clothes : clothes_cnt)
{
answer *= clothes.second + 1;
}
// 문제에서 무조건 1개의 의상은 착용해야 함으로 아무것도 입지 않은 경우 -1
return answer - 1;
}
🔔 왜 이 문제를 백트래킹으로 풀지 않는가?
처음에는 모든 경우를 다 구하는 것이기에 백트래킹을 생각했었다. 하지만 특정한 조건 없이 단순하게 가능한 조합의 개수를 구하는 문제이기 때문에, 각 의상의 종류에 대해 곱의 법칙 연산으로 문제를 해결한다면 O(N) 연산으로 구할 수 있다. 만약 백트래킹을 사용한다면 모든 조합을 탐색해야하고, 종류가 많아질수록 탐색해야 하는 경우의 수가 기하급수적으로 증가하게 되어 O(2^N) 연산으로 비효율적이다.
✔️ 그렇다면 언제 곱의 법칙을 사용하고, 언제 백트래킹을 사용해야할까?
✅ 곱의 법칙이 적용되는 경우
곱의 법칙은 기본적으로 각 선택이 독립적이고, 중복 없이 단순 조합을 구할 때 사용한다. 즉, 특정한 조건 없이 단순히 가능한 조합의 개수를 세는 문제에서는 곱의 법칙이 더 효율적이다.
의상 조합 문제: 위와 같은 문제
비밀번호 만들기: 숫자 4자리 비밀번호를 만들 때의 조합의 개수
주사위 던지기: 2개의 주사위를 굴려 나올 수 있는 경우의 수
✅ 백트래킹이 반드시 필요한 경우
어떤 조건을 만족하는 경우만 선택해야 하는 문제나 최적의 해를 찾는 문제. 모든 경우를 탐색하면서 조건을 만족하는지 확인해야 하는 경우에는 백트래킹이 필수적이다. 특히 "최대", "최소", "길이 제한", "특정 조합만 허용" 같은 조건이 있으면 곱의 법칙은 사용할 수 없다.
