[코딩테스트] 경우의 수, 합의 법칙, 곱의 법칙

경우의 수 

경우의 수는 특정 사건에서 발생할 수 있는 가능한 결과의 총 가짓수를 의미한다.

 

예를 들어, 동전을 던질 때 앞면 또는 뒷면 중 하나가 나오므로 경우의 수는 2가지이다.
주사위를 던지면 1부터 6까지의 숫자가 나올 수 있어 경우의 수는 6가지이다

 

합의 법칙

합의 법칙은 두 사건이 동시에 발생하지 않을 때, 각 사건의 경우의 수를 더하여 전체 경우의 수를 구하는 방법이다.

예를 들어, 한 개의 주사위를 던져 2의 배수 또는 5의 배수가 나오는 경우의 수를 구해보해보자.

• 2의 배수가 나오는 경우: 2, 4, 6 → 경우의 수는 3가지
• 5의 배수가 나오는 경우: 5 → 경우의 수는 1가지
• 따라서, 2의 배수 또는 5의 배수가 나올 경우의 수는 3 + 1 = 4가지이다.

이처럼 합의 법칙은 "또는", "~이거나"와 같은 표현이 등장하며, 각 사건이 동시에 발생하지 않는 경우에 사용된다.

사건 A가 일어나는 경우의 수 a가지
사건 B가 일어나는 경우의 수 b가지일 때, 
사건 A 또는 B가 일어날 경우의 수 = a + b

 

곱의 법칙 

곱의 법칙은 두 사건이 동시에 일어나야 하는 경우 사용된다. 여기서 "동시"는 같은 시각을 의미하지 않고, 각 사건이 모두 발생해야 한다는 뜻이다.

예를 들어, 3종류의 티셔츠와 2종류의 바지가 있을 때, 티셔츠와 바지를 각각 하나씩 선택할 수 있는 경우의 수를 구해보자.

• 티셔츠를 고르는 경우의 수: 3가지
• 바지를 고르는 경우의 수: 2가지
• 따라서, 티셔츠와 바지를 고르는 경우의 수는 3 × 2 = 6가지이다.

곱의 법칙은 "그리고", "동시에"와 같은 표현이 등장하며, 각 사건이 독립적이지만 함께 발생해야 할 때 사용된다.

사건 A가 일어나는 경우의 수가 a가지 
사건 B가 일어나는 경우의 수가 b가지일 때, 
사건 A와 사건 B가 동시에 일어날 경우의 수 = a x b 

 

합의 법칙과 곱의 법칙 문제 

1. 합의 법칙 적용 문제

• 문제 번호: 10797(https://www.acmicpc.net/problem/10797)
• 문제 제목: 10부제
• 문제 설명: 자동차 번호의 끝자리 숫자와 날짜의 일의 자리 숫자가 일치하는 차량만 운행할 수 있을 때, 주어진 차량 번호 중 운행 가능한 차량의 수를 구하는 문제이다. 

 

2. 곱의 법칙 적용 문제

• 문제 번호: 9375(https://www.acmicpc.net/problem/9375)
• 문제 제목: 패션왕 신해빈
• 문제 설명: 여러 종류의 의상 중에서 한 가지 이상의 의상을 선택하여 조합할 때, 가능한 조합의 수를 계산하는 문제이다. 각 의상 종류별로 선택 가능한 옵션이 주어지며, 곱의 법칙을 활용하여 모든 조합을 구한 뒤, 아무것도 입지 않는 경우를 제외한다.