[알고리즘] 4. 과일 공평하게 나누기

1. 기본 문제

• 사과 12개를 3명이 공평하게 가지기 위해서는 몇 개씩 가져가야 할까?

문제 분석

• 12와 n의 최대 공약수가 3

• 12 = 3 * 4로 우리가 쉽게 구할 수 있으나, 코드로는?

• 최대 공약수 공식을 반대로 쫒아가야 함
• GCD(3, 0) = GCD(12, n)
• 12 = n * 3 + 0
• n = 12 / 3

코드 작성

package algo;

public class Gcd02 {
    public static void main(String[] args) {
        int apple = 12;
        int people = 3;

        int value = apple / people;
        System.out.println("한 사람이 받을 사과 개수 : " + value);
    }
}

결과

2. 심화 문제

• 사과🍎 12개, 바나나🍌 18개, 귤🍊 24개를 모든 사람이 공평하게 받기 위해서는 과일을 각각 몇 개씩 받아야 할까?

문제 분석

• 3개의 수의 최대 공약수를 구하는 공식이 필요
• 3개의 수의 최대 공약수 = 2개의 수의 최대 공약수와 나머지 수의 최대 공약수
• gcd(gcd(a,b),c) = gcd(a,(b,c)) = gcd(a,b,c)

코드 작성

• 최대 공약수 코드

package algo;

public class Uc {
    static int gcd(int a, int b) {
        int l = a > b ? a : b;
        int s = a < b ? a : b;

        // System.out.println("a, b 중 더 큰 수는 " + l + ", 더 작은 수는 " + s + "입니다.");
        // div 0 : 나눌 수 없으므로 l이 최대 공약수
        if (s == 0) return l;
            // 그 외 : 유클리드 호제법
        else {
            // 1. 나머지가 0인 경우 : s를 반환
            int r = l % s;
            if (r == 0) return s;
            l = s;
            s = r;
            // 2. 그 외 : 반복
            return gcd(l, s);
        }
    }
}

• 메인 코드

package algo;

public class Gcd03 {
    public static void main(String[] args) {
        int apple = 12;
        int banana = 18;
        int mandarin = 24;

        Uc f = new Uc();
        int g = f.gcd(f.gcd(apple, banana), mandarin);

        System.out.println("사과🍎 : " + apple / g);
        System.out.println("바나나🍌 : " + banana / g);
        System.out.println("귤🍊 : " + mandarin / g);

    }
}

결과