N개의 최소공배수 (programers > lev2 > Number_Change)

문제 링크

문제설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

입출력 예

풀이

	static int gcd(int m, int n) {
		if(m%n==0)
			return n;
		else
			return gcd(n,m%n);
	}
	
	
	static public int solution(int[] arr) {
		//GCD를 구해서 그 GCD로 나누어 떨어지는 몫을 곱해주면 LCM이 된다.	
		
		if(arr.length == 1)
			return arr[0];
		
		else if(arr.length == 2) {
			int g =  gcd(arr[0], arr[1]);
			return g * (arr[0]/g) * (arr[1]/g);
		}
		
		else {
			int g =  gcd(arr[0], arr[1]);
			int l= g * (arr[0]/g) * (arr[1]/g);
				
			for(int i=2; i<arr.length; i++) { 
				g = gcd(l,arr[i]);
				l = g * (l/g) * (arr[i]/g);
			}
			return l;
		}
	}
	

후기 (2h)

항상 풀기 꺼려했었던 최대 공약수, 최소 공배수…

1. 두 수의 최소공배수 = 최대공약수(g)의 g* a/g * b/g
   
2. 여러 수의 최대 공약수 = 두개 계산하고 그 계산한 수를 다시 다음 수와 최대 공약수 계산
   
3. 여러 수의 최소 공배수 = 두 수의 최대 공약수 구한 후 최소 공배수 계산

tip

1. 최대공약수 (GCD)와 최소공배수(LCM)를 구하는 법을 드디어… 다 풀어봤다 이제서야
2. 까먹지않도록 복습 철저히 해야겠다