곱의 법칙

여러 독립적인 선택을 조합할 때, 각 선택지의 개수를 모두 곱해서 전체 경우의 수를 구하는 원리입니다 (Multiplication Principle).

왜 필요한가?

[ 메뉴 조합 ]
음료: 커피, 주스, 물        → 3가지
디저트: 케이크, 쿠키        → 2가지
사이드: 감자튀김, 샐러드      → 2가지

각 선택은 서로 독립 (한 영역의 선택이 다른 영역에 영향 X)

전체 경우의 수 = 3 × 2 × 2 = 12가지

→ 모든 조합을 일일이 나열할 필요 없이 곱셈만으로 계산

합의 법칙과의 차이

법칙언제 쓰나연산
곱의 법칙"A 그리고 B" — 동시·연쇄 선택 (독립)곱하기 (∏)
합의 법칙"A 또는 B" — 배타적 선택더하기 (∑)
 
[ 점심 메뉴 결정 ]

곱의 법칙:
음료(3) × 디저트(2)         → 6가지 (음료와 디저트 둘 다 고르기)

합의 법칙:
음료(3) + 디저트(2)         → 5가지 (음료 또는 디저트 중 하나만 고르기)

"선택 안 함"을 옵션으로 추가하기

일부 영역에서 고를 수도, 안 고를 수도 있을 때:

각 영역의 옵션 수 = (실제 항목 수) + 1
                                ↑
                            "안 고름"이라는 가상의 옵션

[ 예시: 옷장 ]
모자: 빨강, 파랑   → 옵션 3가지: 안 씀 / 빨강 / 파랑
안경: 검정         → 옵션 2가지: 안 씀 / 검정

전체 조합 = 3 × 2 = 6가지
  - 모자 안 씀 + 안경 안 씀
  - 모자 안 씀 + 안경 검정
  - 빨강       + 안경 안 씀
  - 빨강       + 안경 검정
  - 파랑       + 안경 안 씀
  - 파랑       + 안경 검정

위장 문제 풀이 추적

스파이가 옷 조합으로 변장한다. 같은 종류의 옷을 동시에 두 개 입을 수 없다. 적어도 하나는 입어야 한다. 가능한 조합 수는?

public int solution(String[][] clothes) {
    HashMap<String, Integer> map = new HashMap<>();

    for (String[] part : clothes) {
        map.put(part[1], map.getOrDefault(part[1], 0) + 1);
    }

    int answer = 1;
    for (int count : map.values()) {
        answer *= (count + 1);
    }

    return answer - 1;
}

[ 입력 ]
clothes = [
  ["yellow_hat", "headgear"],
  ["blue_sunglasses", "eyewear"],
  ["green_turban", "headgear"]
]

1단계: 종류별 개수 카운트

[ 단계별 추적 ]
초기: { }

["yellow_hat", "headgear"]:
  put("headgear", 1)
       { headgear=1 }

["blue_sunglasses", "eyewear"]:
  put("eyewear", 1)
       { headgear=1, eyewear=1 }

["green_turban", "headgear"]:
  put("headgear", 2)
       { headgear=2, eyewear=1 }

2단계: 곱의 법칙 적용

headgear: 2개 → 옵션 3가지 (안 씀 / yellow_hat / green_turban)
eyewear:  1개 → 옵션 2가지 (안 씀 / blue_sunglasses)

answer = 1
        × 3 (headgear)  → 3
        × 2 (eyewear)   → 6

3단계: "전부 안 씀" 제외

조합 6가지 중 "headgear 안 씀 + eyewear 안 씀"은
"적어도 하나는 입어야 한다"는 조건 위배

→ 6 - 1 = 5

검증: 모든 조합 나열

1. yellow_hat
2. green_turban
3. blue_sunglasses
4. yellow_hat + blue_sunglasses
5. green_turban + blue_sunglasses

→ 5가지 O

비슷한 패턴들

비밀번호 조합 수

4자리 비밀번호, 각 자리 0~9:
10 × 10 × 10 × 10 = 10,000가지

알파벳 + 숫자 조합

3자리 코드: 알파벳(26) → 숫자(10) → 숫자(10)
26 × 10 × 10 = 2,600가지

부분집합 개수

n개의 원소 → 각 원소가 "들어감/안 들어감" 2가지

전체 부분집합 수 = 2^n

// 비트마스크로 구현 시
for (int mask = 0; mask < (1 << n); mask++) {
    // 각 mask가 하나의 부분집합
}

격자 경로 수 (작은 격자)

m × n 격자, 오른쪽/아래만 이동 가능:
경로 수 = C(m+n, m)
        = (m+n)! / (m! × n!)

큰 격자는 조합 nCr 공식 또는 DP 사용

함정: 독립이 아닌 경우

[ 곱의 법칙 적용 불가 케이스 ]

학생 5명 중 회장과 부회장 뽑기:
  회장: 5가지
  부회장: 5가지   X 회장으로 뽑힌 사람은 부회장 X

→ 5 × 5 = 25 (X)
→ 5 × 4 = 20 (O, 순열)

선택이 서로 영향을 주면 곱의 법칙을 그대로 적용 못 함. 순열(P), 조합(C) 등 다른 공식 필요.

시간복잡도

종류 수 K → 각 종류 카운트 후 곱하기 = O(K)
입력 N개 → 카운팅 O(N)

전체: O(N + K)

핵심 정리

곱의 법칙은 여러 독립적인 선택을 조합할 때 각 선택지 수를 곱하는 원리로, 알고리즘 문제에서는 카운팅 자료구조(HashMap 등)와 함께 등장합니다. "선택 안 함"이 허용되는 경우 옵션 수에 +1을 더하고, "전부 선택 안 함"이 답에서 제외돼야 한다면 마지막에 -1을 합니다 (위장 문제 패턴). 단, 선택이 서로 영향을 주는 경우(예: 같은 사람 두 번 못 뽑기)에는 단순 곱이 아닌 순열(P) 또는 조합(C) 공식을 써야 합니다.

CSLOG에서 보기