문제

https://www.acmicpc.net/problem/1934 https://www.acmicpc.net/problem/2609

풀이

  • 유클리드 호제법으로 풀어야 한다
  • 유클리드 호제법이란 두 수 사이에 존재하는 최대공약수를 구하는 알고리즘
  • a를 b로 나눈 나머지가 r이라면 GDC(a, b) = GDC(b, r) r = 0 이면 b가 최대 공약수
  • 예를 들어 GCD(16, 4) = GCD(4, 0) = 최대공약수는 4
  • 최소 공배수는 a * b / 최소공배수
  • GDC의 공식은 작은 수가 0이 될 때 까지 큰수를 작은수로 나누고 몫을 작은 수에 넣고, 기존 작은 수는 큰수에 넣는다

최소공배수, 최대공약수 구하기

import java.util.Scanner;

public class Test{
	
	public static int gcd(int big, int small) {
		while(small != 0) {
			int r = big%small;
			big = small;
			small = r;
		}
		
		return big;
	}
	
	public static void main(String[] args) {
		
        Scanner sc = new Scanner(System.in);
        int arr = 0;				// 최소공배수
        int arr2 = 0;				// 최대공약수

       	int small = sc.nextInt();
        int big = sc.nextInt();
            
        if(big < small) {
        	int temp = small;
        	small = big;
        	big = temp;
        }
           
        arr = gcd(big, small);
        arr2 = big*small / gcd(big, small);
        
        System.out.println(arr);
        System.out.println(arr2);
	}
}

처음 작성한 소스

  • 아래 소스는 2와 3으로 나누어지지 않는 정수( 7, 7 )를 대입할 시 잘못된 값 출력(49)
import java.util.Scanner;

public class Test{
	
	public static void main(String[] args) {
		
		// 최소공배수 구하기
		Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        int[] arr = new int[count];
        
		for(int i = 0; i < count; ++i) {
			int small = sc.nextInt();
			int big = sc.nextInt();
			int value = 1;		// 나누는 수
			
		    while(true) {
	        	if(small <= 1 || big <= 1) {
	        		break;
	        	}
	      
	        	if(0 == small%2 && 0 == big%2) {
	        		small *= small/2;
	        		big *= big/2;
	        		value *= 2;
	        	
	        	}else if(0 == small%3 && 0 == big%3){
	        		// 홀수
	        		small *= small/3;
	        		big *= big/3;
	        		value *= 3;
	        		
	        	}else {
	        		break;
	        	}
	        
	        }
		    
		    
	        int result = 1;
	        if(small != 0) result *= small;
	        if(big != 0) result *= big;
	        if(value != 0) result *= value;
	        //System.out.println("small:"+small+" big:"+big+" value:"+value);
	        
	        arr[i] = result;
		}
		
		for(int i = 0; i < count; ++i ) {
			System.out.println(arr[i]);
		}
	}
}