[JAVA-알고리즘] 4-1 예제

1. 기본문제

사과 12개를 3명이서 공평하게 나누려면 몇 개씩 나누면 될까?

여기서 최대공약수(GCD)를 사용하면 각 사람에게 나눠야 할 개수를 쉽게 구할 수 있어요.

package algo;

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

        // gcd(a,b) = gcd(b, a % b)

        // 12(사과)와 3(사람)의 최대공약수
        // 12(a) % 3(b) = 0(c)
        // 최대공약수는 3
        // 공약수 / 사과

        int a = 12;
        int b = 3;

        int c = a / b;

        System.out.println("사람 한 명당 사과 : " + c + "개 받을 수 있습니다");
    }
}

2. 심화문제

사과 12개 🍎, 바나나 18개 🍌, 귤 24개 🍊을 같은 개수로 최대한 공평하게 나눌 때, 
한 사람당 받을 개수는?

package algo;

public class Gcd03 {
    static int gcd(int a, int b) {

        int c = a % b;
        a = b;
        b = c;

        if (c == 0) {
            return a;
        } else return gcd(a, b);
    }

    public static void main(String[] args) {
        //사과 12개 🍎, 바나나 18개 🍌, 귤 24개 🍊을 같은 개수로 최대한 공평하게 나눌 때, 한 사람당 받을 개수는?
        // gcd(a,b) = gcd(b, a % b)


        int a = 12;
        int b = 18;
        int o = 24;

        int s1 = gcd(b, a); // s1 = 6
        int s2 = gcd(s1, b);

        int apple = a / s1; // 12 % 6
        int banana = b / s1;
        int orange = o / s1;

        System.out.println(s2 + "명에서");
        System.out.println("🍎" + apple + "개");
        System.out.println("🍌" + banana + "개");
        System.out.println("🍊" + orange + "개를 나눠 먹을 수 있다.");
    }
}