[백준/BOJ] 2609번 : 최대공약수와 최소공배수 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

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

---

- 문제 -

 

난이도 실버 5 문제이다.

 

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

최대공약수는 유클리드 호제법으로 풀자.

최소공배수는 두 값중 큰 값을 작은 값으로 나누어떨어질때까지 배를 해준다.

 

유클리드 호제법이란 두 값중 큰 값을 a , 작은 값을 b라고 하자. a를 b로 나눠서 나누어 떨어지면 b가 최대공약수 인 것이다. 나누어떨어지지 않는다면, a에 b값을 저장하고, b에는 a와 b를 나눠서 나온 나머지를 저장한다. 그렇게 다시 a와 b를 나눠서 나누어 떨어지지 않는다면 또 반복한다. 그렇게 나누어떨어지면 b 값이 최대공약수가 되는 것이다.

 

예시를 들자면 48과 46이다. 48은 46으로 나누어 떨어지지 않는다. 나머지는 2이다. 그럼 이제 48대신 46을, 46대신 2로 바꿔 46과 2를 나눈다. 나누어 떨어진다. 그럼 48과 46의 최대공약수는 2인 것이다.

하나를 더 보자.124와 58이다. 나누어 떨어지지 않는다. 나머지는 8이다. 그럼 이제 58과 8을 본다. 나누어 떨어지지 않는다. 나머지는 2다. 8과 2를 본다. 나누어 떨어진다. 그럼 124와 58의 최대공약수는 2가 되는 것이다.

 

최소공배수를 보자. 예를 들어보자. 48과 5이다. 48은 5로 나누어 떨어지지 않는다. 그럼 48의 2배수를 보자. 96이다. 5로 나누어 떨어지지 않는다. 48의 3배수를 보자. 144이다. 5로 나누어 떨어지지 않는다. 48의 4배수를 보자. 192다. 5로 나누어 떨어지지 않는다. 48의 5배수를 보자. 240이다. 5로 나누어 떨어진다. 그럼 최소공배수는 240이다. 5같은 소수로 계산하게 되면 둘이 곱하는게 좋지만 소수인지 판별하게 되면 시간도 오래 걸리고, 코드도 복잡해 지니 이렇게 차례대로 보자.

 

이 두가지 방법으로 푼다. 코드를 보자.

 

항상 코드를 짤때 제일 고민되는 것은 변수명을 정하는 것이다.... 이번에도 멀로 할지 생각하다가 결국 그냥 느낌대로 해버렸다... 변수의 개수가 코딩의 길이에 비해 좀 있다보니 변수가 바로 이해가 안될 수 있다. 잘 봐서 이해하길 바라겠다...

---

-풀이-

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int max = Math.max(N, M);
		int min = Math.min(N, M);
		int a = max;
		int b = min;
		
		//b출력까지 유클리드 호제법(최대공약수 구하기)
		while(a % b != 0) {
			int a_b = a;
			a = b;
			b = a_b % b;
		}
		System.out.println(b);
		
		//max 출력까지 최소공배수 구하기
		int i = max;
		while(max % min != 0) {
			max += i;
		}
		System.out.println(max);
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.