백준알고리즘 2609번 최대공약수와 최소공배수 C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 2609
• 문제명: 최대공약수와 최소공배수
• 언어: C#
• 분류: 수학, 정수론, 유클리드 호제법
• 비고: 

 

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

 

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

 

풀이

최대공약수와 최소공배수는 항상 자연수로 구성되며 0은 일반적으로 자연수가 아님을 명심해야 한다.

수를 나눌 때 가장 작은 공약수로 나누는 것부터 시작하면 더 나눌 수 있는데 나눠지지 않고 그냥 넘어갈 수 있기에 가장 큰 공약수로 나누는 것부터 시작해야 깔끔하게 나눌 수 있다.

// 문자열로 두 자연수를 입력받아 공백으로 구분
string[] input = Console.ReadLine().Split();

// 문자열 형태의 자연수를 정수로 전환해 배열에 배치
int[] number = new int [2];
number[0] = Convert.ToInt32(input[0]);
number[1] = Convert.ToInt32(input[1]);
// 오름차순으로 배열 정렬
Array.Sort(number);

// 최대공약수 the greatest common denominator
int gcd = 1;
// 최소공배수 the least common multiple
int lcm = 1;

// 배열에 입력한 가장 작은 수부터 시작해 1씩 차감하며 1에 도달할 때까지 반복
for(int i = number[0]; i >= 1; i--)
{
    // 두 수의 공약수들로만 나눠진다. 
    if (number[0] % i == 0 && number[1] % i == 0)
    {
        // 최대공약수에 나눌 때 사용한 수를 곱한다
        gcd *= i;
        // 최소공배수에 나눌 때 사용한 수를 곱한다
        lcm *= i;
        // 배열 내 수를 최대한 큰 수로 나누어 크기를 줄인다
        number[0] /= i;
        number[1] /= i;
    }
}

// 최종적인 최소공배수 완성을 위해 더 이상 나눌 수 없는 배열의 수를 곱한다.
lcm *= number[0] * number[1];

// 최대공약수 출력
Console.WriteLine(gcd);
// 최소공배수 출력
Console.WriteLine(lcm);

 

후기

처음 시도했을 때 유클리드 호제법을 어설프게 시도하다가 실패했다. 큰 수를 작은 수로 나눈 나머지가 곧 최대공약수라고 생각했으나 아니었다. 변수 문제를 의심해서 최대공약수와 최소공배수의 초기값을 0으로 안 해서 그런 줄 알기도 했다. 하지만 앞서 말했듯이 자연수라는 전제 조건을 믿었기에 초기값 문제라는 생각은 사그라들었다. 그리하여 공약수로 나눌 때 가장 큰 공약수로 시작해야 제대로 나눠진다는 것을 알았다. 오늘도 하나 배웠다.