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

문제 링크

2609번: 최대공약수와 최소공배수

 

www.acmicpc.net

 

---

주의사항

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

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

---

문제 설명

---

접근 방법

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

 

최대 공약수:  for문을 통하여 반복하여 입력된 숫자보다 작은 자연수에 가장 큰 공약수를 찾도록 하였습니다.

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

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 사용하여 입력값을 띄어쓰기 기준으로 나누어 숫자를 저장하였습니다.
• 최대 공약수 구하는 함수 GCD과 최소 공배수 구하는 함수 LCM를 만들었습니다.
• 함수 결과값을 BufferedWriter에 저장하였습니다.
• BufferedWriter을 사용하여 결과를 출력하였습니다.

• for문을 사용하여 LCM와 GCF을 구성하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	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를 통해 결과 값 출력
        //-------------입력값 저장----------------
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	int num1 = Integer.parseInt(st.nextToken());
    	int num2 = Integer.parseInt(st.nextToken());
        //결과 BufferedWriter에 저장
    	bw.write( GCD(num1,num2)+ "\n" + LCM(num1, num2) + "\n");
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
	}
	//-----------최대 공약수 구하는 함수------------
	public static int GCD(int num1, int num2) {
		int result = 0;
		for(int i=1;i<=num1;i++) {
			if(num1%i != 0)
				continue;
			if(num2%i==0) {
				result = i;
			}
		}
		return result;
	}
	//-----------최소 공배수 구하는 함수----------------
	public static int LCM(int num1, int num2) {
		int curnum1 = num1;
		int curnum2 = num2;
		while(true) {
			if(curnum1>curnum2)
				curnum2 +=num2;
			else if(curnum1<curnum2)
				curnum1 +=num1;
			else
				break;
		}
		return curnum1;
	}
}