[네이버클라우드 캠프/3주차] 최소공배수와 최대공약수 출력하기

고등수학에서 두 수의 최소공배수와 최대공약수를 구하기 위해서는 조립제법을 사용합니다.

조립제법을 통해 직관적으로 보이는 수를 곱하여 최소공배수 혹은 최대공약수를 구합니다.

 

이러한 최소공배수와 최대공약수를 어떻게 프로그램(알고리즘)으로 작성해야 하는지.. 참 많이 고민되었습니다.

 

❓ 문제 : 사용자에 두 정수를 입력받아, 최소공배수와 최대공약수를 출력하세요.

 

1. 생각 정리

최대공약수는 for문을 통해 사용자가 입력한 두 수에 대해 공통적으로 나눠지는 수를 구해야겠다고 생각했습니다.

그러나 사용자가 큰 수를 입력하는 경우를 대비하여 많은 횟수를 반복하지 못하도록 제한하는 것이 필요했습니다.

(처음에는 어떤 기준으로 반복 횟수를 제한해야할지 감조차 오지 않았습니다.)

 

이를 위해 min이라는 int형 변수를 선언하여, 입력 받는 두 수 중 더 작은 수를 찾았고

min 이하의 수들 중 함께 나눠지는(약분되는) 수를 찾았습니다.

 

그리고 대망의 최소공배수...

처음엔 최대공약수로 두 수를 나누어 나오는 몫을 최대공약수와 곱해야겠다는 생각을 했습니다. (조립제법 원리)

 

이 방법도 정답이겠지만, 최소공배수를 구하는 식을 자세히 들여다보니

입력받은 두 수의 곱을 최대공약수로 나눠주기만 하면 된다는 것을 깨달았습니다.

 

2. 최종 소스코드

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("1번째 정수 입력 > "); int n = sc.nextInt(); sc.nextLine();
		System.out.print("2번째 정수 입력 > "); int m = sc.nextInt(); sc.nextLine();
		
		int min = n > m ? m : n; // 두 정수 중 최소값 찾기
		
		int gcd = 1; // 최대공약수
		
		for(int i = 1; i <= min; i++) {
			if(n%i == 0 && m%i == 0) {
				gcd = i; // 마지막에 담기는 수가 최대공약수
			}
		}
		
		int lcm = n * m / gcd; // 최소공배수
		
		System.out.println("최대공약수 : " + gcd);
		System.out.println("최소공배수 : " + lcm);
	}
}

 

🙏🏻 마무리

이번 문제를 통해 기존에 알고 있던 수학 공식을 활용해 문제를 풀어나갈 수 있겠지만,

더 쉽고, 더 간단하게 풀이할 수 있는 방법에 대해 더 많이 고민해야겠다는 생각이 들었습니다.

수학과 함께 코드에 대해 얘기하니 더 재밌는 것 같습니다. 다음 문제는 제가 더 똑똑하게 풀 수 있기를 바라며...

긴 글 읽어주셔서 감사합니다 🙏🏻