Cos Pro 1급 - 샘플 문제 5차 8번 - 최대공약수 구하기(유클리드 호제법)

문제 지문 #8

세 수 a, b, c의 공약수가 몇 개인지 구하려고 합니다. 공약수란, 동시에 모든 정수의 약수인 정수를 뜻합니다. 예를 들어, 세 수 24, 9, 15의 공약수는 1, 3이고, 따라서 양의 공약수는 2개입니다.

세 수의 공약수가 몇 개인지 구하기 위해 다음과 같이 프로그램 구조를 작성했습니다.

1. 세 수의 최대공약수를 구합니다.
2. 앞서 구한 최대공약수의 약수가 몇 개인지 구합니다.

세 수 a, b, c가 매개변수로 주어질 때, 세 수의 약수가 몇 개인지 return 하도록 solution 메서드를 작성하려 합니다. 위 구조를 참고하여 코드가 올바르게 동작할 수 있도록 빈칸에 주어진 func_a, func_b, func_c 메서드와 매개변수를 알맞게 채워주세요.

---

#####매개변수 설명

세 수 a, b, c가 매개변수로 주어집니다.

• 세 수 a, b, c는 1 이상 1,000 이하인 정수입니다.

---

#####return 값 설명

세 수의 약수가 몇 개인지 return 합니다.

---

#####예제

a	b	c	return
24	9	15	2

#####예제 설명
문제에 나온 예와 같습니다.

728x90

 

혼자 풀이

빈칸 채우기 문제입니다. 주어진 세 수의 최대공약수의 약수의 개수를 구하는 문제입니다.

최대공약수의 개수를 구하는 가장 간단한 방법은 a, b, c 중 가장 작은 수 이하의 모든 수로 나누어 최대공약수를 찾고, 그 최대공약수의 약수의 개수를 구하는 방법입니다. (Bruteforce)

class Main {	
	
	public int solution(int a, int b, int c) {

		int answer = 0;
		
		int min,gcd;
		
        //세 수의 최대공약수는 세 수 중 가장 작은 수보다 작다
		min=Math.min(Math.min(a,b),c);
		for(int i=min;i>0;i--){
			if(a%i==0 && b%i==0 && c%i==0){//세 수를 나눌 수 있는 가장 큰 수가 최대공약수
				gcd=i;
				break;
			} 
		}
		
		for(int i=1;i<=gcd;i++){  //최대공약수의 약수의 개수를 구함
			if(gcd%i==0) answer++;
		}
			
		return answer;
	}

	// 아래는 테스트케이스 출력을 해보기 위한 main 메소드입니다.
	public static void main(String[] args) {
		Main sol = new Main();
		int a = 24;
		int b = 9;
		int c = 15;
		int ret = sol.solution(a, b, c);

		// [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
		System.out.println("solution 메소드의 반환 값은 " + ret + " 입니다.");
	}
}

Output:

solution 메소드의 반환 값은 2 입니다.

그런데, 이 문제에서는 조금 다른 방법을 사용하고 있습니다. 유클리드 호제법이라는 것인데요.
유클리드 호제법은 A와 B의 최대공약수를 구할 때, A와 B의 최대공약수가  B와 A를 B로 나눈 나머지의 최대공약수와 같다는 법칙을 이용하여 계산하는 방법입니다.

A가 B보다 클 때, A를 B로 나눈 나머지가 C0라면, B를 C0로 나누어 그 나머지를 C1이라고 하고, C0를 다시 C1으로 나누는 식으로 나머지가 0이 될 때까지 나누어서 나머지가 0이 될 때의 Cn이 최대공약수가 됩니다.

예를 들어, 24와 18의 최대 공약수라고 하면 아래와 같이 최대공약수를 구할 수 있습니다.

24(A) % 18(B) = 6(C0)
18(B) % 6(C0) = 0(C1) 

위 예에서 나머지가 0이 될 때의 Cn인  6(C0)이 최대 공약수가 됩니다.

유클리드 호제법은 큰 수의 최대공약수를 구할 때, 무차별 대입(bruteforce)보다 시간 복잡도가 낮기 때문에 사용합니다.

class Main {
    //유클리드 호제법은
    //a와 b의 최대공약수를 구할때
    //a와 b의 최대공약수가 b와 a%b의 최대공약수가 같다는 법칙을 이용하여 계산하는 방법
    //계속 연산을 이어나가다가 나머지가 없을 때의 b가 최대공약수가 됨
    //큰 수의 최대공약수를 구하기 위해 사용함
    public int func_a(int a, int b) {  //유클리드 호제법으로 최대공약수를 구함
        int mod = a % b;

        while(mod > 0) { //mod가 0이 될 때 b의 값이 최대 공약수
            a = b;
            b = mod;
            mod = a % b;
        }
        return b;
    }

    public int func_b(int n) { //최대공약수의 약수의 개수를 구함
        int answer = 0;

        for(int i = 1; i <= n; i++) { 
            if(func_c(n,i))
                answer++;
        }
        return answer;
    }

    public boolean func_c(int p, int q) { //q가 p의 약수인지 체크
        if(p % q == 0)
            return true;
        else
            return false;
    }
	
    public int solution(int a, int b, int c) {
        int answer = 0;

        int gcd = func_a(func_a(a,b),c);  //최대공약수를 구함
        // answer = func_@@@(@@@);
        answer = func_b(gcd); //수정한 부분 최대공약수의 약수를 구함
        return answer;
    }

    // 아래는 테스트케이스 출력을 해보기 위한 main 메소드입니다.
    public static void main(String[] args) {
        Main sol = new Main();
        int a = 24;
        int b = 9;
        int c = 15;
        int ret = sol.solution(a, b, c);

        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("solution 메소드의 반환 값은 " + ret + " 입니다.");
    }
}

Output:

solution 메소드의 반환 값은 2 입니다.

 

정답

혼자 풀이와 정답이 동일합니다.

실습은 아래 참고

2022.10.25 - [Programming/Cos Pro 1급] - Cos Pro 1급 공부 사이트 추천 - 구름 에듀(https://edu.goorm.io/)

Cos Pro 1급 공부 사이트 추천 - 구름에듀(https://edu.goorm.io/)