[자료구조] 경우의 수

1. 경우의 수

• 어떤 사건에서 일어날 수 있는 경우의 가짓수
• ex) 동전을 던지는 사건: 경우의 수 - 2
• ex) 주사위를 던지는 사건: 경우의 수 - 6
• 사건 A가 일어날 경우의 수: n(A)

2. 합의 법칙

• 사건 A 또는 사건 B가 일어날 경우의 수
• 사건 A와 사건 B의 합의 법칙: n(A ∪ B)
• n(A ∪ B) = n(A) + n(B) - n(A ∩ B)

3. 곱의 법칙

• 사건 A와 사건 B가 동시에 일어날 경우의 수
• 사건 A와 사건 B의 곱의 법칙: n(A x B)
• n(A x B) = n(A) x n(B)

4. 코드

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

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

// 1. 합의 법칙
// 두 개의 주사위를 던졌을 때 합이 3 또는 4의 배수일 경우의 수

// 1 - 기본 풀이
for (int item1:dice1) {
	for(int item2:dice2) {
    	if((item1 + item2) % 3 == 0) {
        	nA += 1;
        }
        if((item1 + item2) % 4 == 0) {
        	nB += 1;
        }
        if((item1 + item2) % 12 == 0) {
        	nAandB += 1;
        }
    }
}
int result = nA + nB - nAandB;

// 2 - HashSet
HashSet<ArrayList> allCase = new HashSet<>();

for (int item1:dice1) {
	for (int item2:dice2) {
    	if((item1 + item2) % 3 == 0 || (item1 + item2) % 4 == 0) {
        	ArrayList list = new ArrayList(Arrays.asList(item1, item2));
            allCase.add(list);
        }
    }
}
int result = allCase.size();

// 2. 곱의 법칙
// 두 개의 주사위 a, b를 던졌을 때 a는 3의 배수, b는 4의 배수인 경우의 수
for (int item1:dice1) {
	if(item1 % 3 == 0) {
    	nA++;
    }
}

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