경우의 수 구하기 (합의 법칙, 곱의 법칙)

1. 합의 법칙

 

합의 법칙은 A에서 발생되는 case 와 B에서 발생되는 case 를 더하는 법칙이다.

이때 중요한건 A와 B에서 겹치는 case 는 빼 주어야한다.

 

집합으로 따지면 합집합과 같다.

n(A U B)=  n(A) + n(B) - n(A ∩ B)

 

---

 

예제 - 두 개의 주사를 던졌을 때 합이 3 또는 4의 배수일 경우의 수 

 

3의 배수의 경우의 수 : 12

 

3 : (1, 2) (2, 1)

6 : (1, 5) (2, 4) (3, 3) (4, 2) (5, 1)

9 : (3, 6) (4, 5) (5, 4) (6, 3)

12 : (6, 6)

 

4의 배수의 경우의 수 : 9

 

4 : (1, 3) (2, 2) (3, 1)

8 : (2, 6) (3, 5) (4, 4) (5, 3) (6, 2)

12 : (6, 6)

 

위 두가지 경우에서 (6, 6)이 겹치는 case 가 된다.

 

따라서 두 개의 주사를 던졌을 때 합이 3 또는 4의 배수일 경우의 수는 12 + 9 - 1 = 20 이 된다.

 

int[] dice1 = {1, 2, 3, 4, 5, 6};
int[] dice2 = {1, 2, 3, 4, 5, 6};

int nA = 0;
int nB = 0;
int nAandB = 0;

// 기본 풀이

for(int item1 : dice1){ // 3의 배수
    for (int item2 : dice2){
        if((item1 + item2) % 3 == 0){
            nA++;
        }
    }
}

for(int item1 : dice1){ //4의 배수
    for (int item2 : dice2) {
        if((item1 + item2) % 4 == 0){
            nB ++;
        }
    }
}

for(int item1 : dice1){ // 3의 배수이면서 4의 배수인 경우
    for (int item2 : dice2) {
        if((item1 + item2) % 12 == 0){
            nAandB ++;
        }
    }
}

System.out.println("두 개의 주사를 던졌을 때 합이 3 또는 4의 배수일 경우의 수 : " + (nA + nB - nAandB));

 

배수를 구할 때는 % (나머지) 연산을 이용하여 구한다.

 

3의 배수이면서 4의 배수인 수는 3과 4의 최소 공배수인 12가 된다.

 

---

 

HashSet 을 이용하여 합의 법칙 구현

 

HashSet<ArrayList> dice = new HashSet<ArrayList>();
for (int item1 : dice1){
    for(int item2 : dice2){
        if((item1 + item2) % 3 == 0 || (item1 + item2) % 4 ==0){
            ArrayList l = new ArrayList(Arrays.asList(item1, item2));
            dice.add(l);
        }
    }
}

System.out.println(dice.size());

 

HashSet 은 중복을 허용하지 않는다는 장점이 있다.

첫번째 코드에서는 중복인 경우를 빼주었는데 HashSet 을 이용하면 중복인 경우가 인수로 들어가지 않아 중복된 경우를 별도로 계산하여 뺄 필요가 없다.

 

ArrayList l = new ArrayList (Arrays.asList(item1, item2))

배열을 list 로 변환하는 코드이다. 

 

dice 는 ArrayList 형태로 된 HashSet 이며 dice.add(l) 를 통해서 item1, item2 를 list 로 만든 l 을 HashSet 에 추가해준다.

 

총 경우의 수는 HashSet 의 크기로 알수 있으며, HashSet 의 크기는 size() 를 통해서 알 수 있다.

 

---

2. 곱의 법칙

 

곱의 법칙이라는 A 와 B 가 동시에 발생되는 경우를 말한다.

각각의 경우가 발생되는 수를 곱해주면 된다.

 

n(A X B)=  n(A) X n(B)

 

---

 

예제 - 두 개의 주사위 a, b를 던졌을 때 a는 3의 배수, b는 4의 배수인 경우의 수

 

a 가 3의 배수인 경우는 (3, 6) 2 가지 이며, b 가 4의 배수인 경우는 (4) 1개 이다.

동시에 나올 수 있는 경우의 수는 2 x 1 = 2 이다.

 

int nA = 0;
int nB = 0;

for (int item1 : dice1){
    if(item1 % 3 == 0){
        nA++;
    }
}

for (int item2 : dice2){
    if(item2 % 4 == 0){
        nB++;
    }
}

System.out.println("두 개의 주사위 a, b를 던졌을 때 a는 3의 배수, b는 4의 배수인 경우: "+(nA * nB));

 

곱의 법칙도 합의 법칙에서 구한 방식으로 경우의 수를 구한 다음 마지막에 곱해주면 된다.