프로그래머스 C# 최대공약수와 최소공배수

문제

 

해결방안

public class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[] {};
        
        int min = GCD(n,m);
        int max = LCM(n,m,min);
        
        answer = new int[]{min,max};
        return answer;
    }
    
     int GCD(int a_, int b_)
        {
            if (b_ == 0) return a_;
            else return GCD(b_, a_ % b_);
        }  
    
     int LCM(int a_, int b_, int gcd_)
        {
            if (gcd_ == 0) return 0;
            int result = (a_ * b_) / gcd_;
            return result;
        }
}

 

이번문제는 꽤 애를 먹었다. 최대공약수와 최소 공배수를 구하는 공식을 알고있지도 않았고,

또한 그것을 어떻게 공식으로 유도해서 프로그램으로 풀어내야할지 막막했어서,

구글에서 검색해본 결과 유클리드의 호재법을 알게되었다.

 

GCD 함수는 최대 공약수를 알아내는 재귀함수로, 한쪽이 0이 될때까지 두 수를 바꿔가며 나머지를 구하는 방식이다.

LCM 함수는 최소 공배수를 알아내는 함수로, 두 수를 곱하고 나온 값을 최대 공약수로 나누는 방식이다.

 

유클리드의 호재법에 관한 내용은 아래 유튜브에서 확인해볼 수 있다.

https://youtu.be/Obs-HC5j5bI?si=4oJZg-XriygXKdwl