[정올 Begginer_Coder - 수학1] 1002.최대공약수, 최소공배수_자바JAVA

 

[ 문제 ]  정올 1002.최대공약수, 최소공배수

문제 링크 : www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=281&sca=2030

JUNGOL

 

 

---

 

[ 입출력 ]

---

 

[ 풀이 ]

 

< 접근 방법 및 풀이 >

• 숫자가 세개 이상일때 두개씩 최대공약수와 최소공배수 구하기.
•  두 숫자 A, B 의 곱은 A, B의 최대공약수 * 최소공배수이다.
• 즉, 최소공배수 = (A * B) / GCD(최대공약수) 이다.
• 두개의 수 A와 B의 최대공약수를 D라 하면, 세개의 수 A, B , C의 최대공약수는 D와 C의 최대공약수와 같다.
•  ex) 세 숫자: 4(A), 8(B), 10(C)이 있다면
•  먼저 4, 8 의 최대공약수와 최소공배수를 구한다.  GCD : 4, LCM : 8
•  구한 최대공약수 4 와 10의 최대공약수를 구하면 GCD : 2
•  구한 최소공배수 8 과 10의 최소공배수를 구하면 LCM: 40
•  따라서 세 숫자 4, 8, 10의 최대공약수 = 2, 최소공배수는 40이다.
•  위와 같은 방식으로 반복문 돌리면 된다. 

 

 

< 주의할 점 >

• 처음에 먼저 최대공약수 다 구하고 최소공배수 구하려고 했더니, 난 그냥 숫자가 몇개가 되든 최대공약수로 나누고 난 나머지 몫들 다 곱하면 최소공배수인 줄 알았는데, 그게 아니었다.
• 각 숫자를 최대공약수로 나누고, 몫들의 값이 서로 서로소인 상태까지 계속 나눠야 최소공배수였다는 걸 뒤늦게 깨달았다. 
•  숫자가 3개 이상일때는 두수씩 따로따로 최대공약수와 최소공배수를 구해서 푸는게 최선이다
• Hint 참고하기

 

---

 

JAVA코드

package 수학1;

import java.util.Scanner;

public class 최대공약수_최소공배수_1002 {


	public static void main(String[] args) {
		Scanner sc = new Scanner (System.in);
		int n = sc.nextInt();
		int arr[] = new int[n];
		
		
		for(int i = 0; i < n; i++) {
			arr[i] = sc.nextInt(); //입력
		}
		
		int GCD = arr[0], lCM = arr[0]; //최대 공약수, 최소 공배수
		//두 수 씩 비교하기 
		for(int i = 1; i < n; i++ ) {
			GCD = get_GCD(GCD, arr[i]); 
			lCM = (lCM * arr[i]) / get_GCD(lCM, arr[i]);
		}
		System.out.println(GCD + " " + lCM);
	}

	private static int get_GCD(int a, int b) {
		int GCD = 0;
		int min = Math.min(a, b);
		for (int i = 1; i <= min ; i++) {
			if(a % i == 0 && b % i == 0) {
				GCD = i;
			}
		}
		return GCD;
		
	}
}

---

 

REVIEW

 

쉬운문제에 많은 시간을 썼다.. 이래서 기초부터 다지라고 하는구나ㅠㅠ..

최대공약수와 최소공배수 헷갈렸는데 다음에 나오면 잘 풀어야지!

최소공배수는 최대공약수를 먼저 구하고,

두 수의 곱 = 최소공배수 * 최대공약수

잊지말기!