[백준] 단계별로 풀어보기(단계:17,정수론 및 조합론,JAVA)1934번, 최소 공배수

문제 링크

1934번: 최소공배수

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에서 규칙에 대한 알고리즘을 살펴보면 (첫 번째 숫자 = num1, 두 번째 숫자 = num2)

처음 문제를 접근할 때에 아래와 방식으로 접근하려고 했으나 1, 45000이 나오면 시간 초과가 발생할 것이라고 생각하여 정규화된 알고리즘이 있나 구글링을 진행하였습니다.

 

최소 공배수:  for문을 통하여 반복하여 입력된 두 숫자를 증가시키면서 같아지면 반복을 종료하고 종료 당시에 값이 최소 공배수의 값이 됩니다.

 

최소공배수를 구하는 공식으로 (num1*num2)/최대공약수

최대 공약수를 구하는 공식으로 구글링을 통해 아래의 위키백과를 참고하여 알고리즘을 작성하였습니다.

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

ko.wikipedia.org

간단히 말해서 num1을 num2로 나누어 떨어지지 않으면 남는 나머지를 num2에 다시 나누어서 또 떨어지지 않는다면 나머지를 구하여 나누는 값을 다시 나누어 떨어지는지 확인하는 것으로 예제를 보여줄 것이지만 자세한 내용을 확인하시고 싶은 분은 위 링크를 확인해주시면 감사드리겠습니다.

예를 들어 입력값이 128, 84일 때

128 = 84 * 1 + 44 으로 나누어 떨이지지 않는다.

84 = 44 * 1 + 40 으로 나누어 떨어지지 않는다.

44 = 40 * 1 + 4 으로 나누어 떨어지지 않는다.

40 = 4* 10 + 0 나누어 떨이지기 때문에 최대 공약수는 4입니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 사용하여 입력값을 띄어쓰기 기준으로 나누어 숫자를 저장하였습니다.
• 최대 공약수 구하는 함수 GCD를 만들었습니다.(유클리드 호제법)
• 입력값의 곱/최대 공약수의 값을 BufferedWriter에 저장하였습니다.
• BufferedWriter을 사용하여 결과를 출력하였습니다.

• GCD는 유클리드 호제법을 이용하여 작성하였습니다.
• 유클리드 호제법은 위에 위키백과 링크에 내용입니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int index;		//입력값 개수
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	//BufferedWriter를 통해 결과 값 출력
        //---------입력값 저장-----------
    	index = Integer.parseInt(br.readLine());
    	for(int i=0;i<index;i++) {
        	StringTokenizer st = new StringTokenizer(br.readLine()," ");
        	int num1 = Integer.parseInt(st.nextToken());
        	int num2 = Integer.parseInt(st.nextToken());
        	bw.write( (num1*num2)/GCD(num1,num2) + "\n");
    	}
    	bw.flush();	//결과 출력
    	bw.close();
    	br.close();
	}
	//-----------최대 공약수 구하는 함수----------------
	public static int GCD(int num1, int num2) {
		if(num2==0)
			return num1;
		else
			return GCD(num2, num1%num2);
	}
}