경우의 수 (The Number Of Cases)

: 어떤 사건에서 일어날 수 있는 경우의 가짓 수

• ex) 동전을 던지는 사건의 경우의 수 2
• ex) 주사위를 던지는 사건의 경우의 수 6
• 일반적으로 다음과 같이 표현한다.
  • 사건 A가 일어날 경우의 수 : n(A)

합의 법칙

• 사건 A 또는 사건 B가 일어날 경우의 수
• OR 연산, 합집합
• ex) 두 개의 주사위를 던졌을 때, 합이 3 또는 4의 배수일 경우의 수는?
  • 사건 A : 합이 3의 배수(3, 6, 9, 12)인 경우 총 12가지
  • 사건 B : 합이 4의 배수(4, 8, 12)인 경우 총 9가지
  • 사건 A와 사건 B의 경우 중, 동일한 경우 : [6, 6] 총 1가지
  • 사건 A의 경우의 수 + 사건 B의 경우의 수 - 사건 A, 사건 B 중복 케이스
  • 답 : 12 + 9 -1 = 20가지 이다.

곱의 법칙

• 사건 A와 사건 B가 동시에 일어날 경우의 수
• 사건 A와 사건 B의 곱의 법칙
• ex) 두 개의 주사위 a, b를 던졌을 때, a는 3의 배수, b는 4의 배수인 경우의 수
  • 사건 A : a가 3의 배수일 경우 총 2가지(3, 6)
  • 사건 B : b가 4의 배수일 경우 총 1가지(4)
  • 사건 A의 경우의 수 X 사건 B의 경우의 수
  • 답 : 2 X 1 = 2

예제

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) {

//        합의 법칙
//        두 개의 주사위를 던졌을 때, 합이 3 또는 4의 배수일 경우의 수
        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) {
            for (int item2: dice2) { // 주사위 두개로 이중 for 문
                if ((item1 + item2) % 3 == 0) { // 3으로 나눈 나머지가 0 = 3의 배수
                    nA+=1;
                }

                if ((item1 + item2) % 4 == 0) { // 4으로 나눈 나머지가 0 = 4의 배수
                    nB +=1;
                }

                if ((item1 + item2) % 12 == 0) { // 12로 나눈 나머지가 0 = 3과 4의 공배수
                    nAandB += 1;
                }
            }
        }
        System.out.println("결과 : " + (nA + nB - nAandB));

//        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);
                }
            }
        }

        System.out.println("결과: " + allCase.size());

//        곱의 법칙
//        두 개의 주사위 a, b를 던졌을 때, a는 3의 배수, b는 4의 배수인 경우의 수
        nA = 0;
        nB = 0;

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

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

        System.out.println("결과 : " + (nA * nB));
    }
}

약수, 최대 공약수, 최대 공배수 구하기

import java.util.ArrayList;
//        약수 구하기, 두 수의 최대공약수와 최소공배수 구하기
//              -> 쉬운 문제에 해당하지만, 해당 개념을 응용해서 출제 빈도 높음
//        1. 1 - 10 의 수 중, A의 약수 또는 B의 약수인 경우의 수
//        2. 1 - 10 의 수 중, A의 약수이면서, B의 약수인 경우의 수

class Practice {

    //        약수
    public ArrayList getDivisor(int num) {
        ArrayList result = new ArrayList();

        for (int i = 1; i <= (int) num/2; i++) {
            if (num % i == 0) {
                result.add(i);
            }
        }
        result.add(num);

        return result;
    }

//    최대 공약수, GCD (the Greatest Common Denominator)
    public int getGCD(int numA, int numB) {
        int gcd = -1;

//        약수 구하기
        ArrayList divisorA = this.getDivisor(numA);
        ArrayList divisorB = this.getDivisor(numB);

//        약수들 중에서 최대 공약수 구하기
        for (int itemA: (ArrayList<Integer>)divisorA) {
            for (int itemB: (ArrayList<Integer>)divisorB) {
                if (itemA == itemB) { // 같은 약수 발견
                    if (itemA > gcd) { // 그리고 그 약수가 gcd보다 크면,
                        gcd = itemA; // gcd에 그 값이 할당
                    }
                }
            }
        }
        return gcd;
    }

//    최소 공배수, LCM
//    LCM : the Lowest Common Multiple
    public int getLCM(int numA, int numB) {
        int lcm = -1;
        int gcd = this.getGCD(numA, numB);

        if (gcd != -1) {
            lcm = numA * numB / gcd;
        }

        return lcm;
    }
}

public class Main {
    public static void main(String[] args) {

//        Test code
        int num1 = 10;
        int num2 = 6;

        Practice p = new Practice();
        ArrayList l1 = p.getDivisor(num1);
        ArrayList l2 = p.getDivisor(num2);
        System.out.println("l1 = " + l1);
        System.out.println("l2 = " + l2);

        System.out.println("최대 공약수 : " + p.getGCD(num1, num2));
        System.out.println("최소 공배수 : " + p.getLCM(num1, num2));

    }
}