C#으로 풀기 - 최대공약수와 최소공배수

Amberjack·2024년 3월 8일
0

Codekata

목록 보기
14/16
post-custom-banner

문제 풀이

오늘은 문제를 풀진 않았다. 대신 gcd와 lcm을 구하는 방법이 있었는데? 하면서 검색을 했다..
대신 이번 기회에 다시 한번 확인을 했기 때문에 다음 번에는 기억하도록 노력해야겠다.

public class Solution
{
    public int[] solution(int n, int m)
    {
        int[] answer = new int[2];

        answer[0] = n >= m ? Gcd(n, m) : Gcd(m, n);
        answer[1] = n * m / answer[0];

        return answer;
    }

    public int Gcd(int a, int b)
    {
        if (b == 0) return a;
        else return Gcd(b, a % b);
    }
}

answer[0]은 gcd, answer[1]은 lcm을 구하여 return 했다.

최대공약수

gcd를 먼저 구하는데, 재귀 함수를 사용하여 구했다.

public int Gcd(int a, int b)
{
	if (b == 0) return a;
	else return Gcd(b, a % b);
}

최소공배수

먼저 gcd를 구한 이유는 바로 lcm을 구할 때 gcd가 사용되기 때문이다.

gcd를 사용하여 lcm을 구하게 되면 함수가 필요 없을 정도로 방법이 쉬워진다.

최소공배수 = n * m / n과 m의 최대공약수 이기 때문이다.

따라서 위에서는
answer[1] = n * m / answer[0]; 혹은 answer[1] = n * m / Gcd(n, m);으로 구하면 된다. 물론 n > m일 때이지만.

post-custom-banner

0개의 댓글