👀 문제 설명
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
예제 입력 1
24 18
예제 출력 1
6
72
✍🏻풀이
최대공약수는 유클리드 호제법을 이용해서 풀고, 최소공배수는 큰 수 * (작은 수 / 최대공약수)를 해서 구하면 된다.
유클리드 호제법은 다음 링크를 참고해 공부했다.
코드
package boj;
// 최대공약수와 최소공배수 (https://www.acmicpc.net/problem/2609 )
import java.util.*;
import java.io.*;
public class BOJ_2609 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
// 최대공약수 - 유클리드 호제법
int bigNum = Math.max(a, b);
int smallNum = Math.min(a, b);
while (smallNum != 0) {
int mod = bigNum % smallNum;
bigNum = smallNum;
smallNum = mod;
}
// 최소공배수
int gcd = bigNum;
int lcm = a * b / gcd;
bw.write(gcd + "\n" + lcm + "\n");
bw.flush();
bw.close();
}
}
'숨막히는 알고말고 > 문제 풀이' 카테고리의 다른 글
[Baekjoon] 블랙잭 (0) | 2021.08.16 |
---|---|
[Baekjoon] 수 정렬하기 2 (0) | 2021.08.16 |
[Baekjoon] 카드2 (0) | 2021.08.15 |
[Baekjoon] 팰린드롬수 (0) | 2021.08.14 |
[Baekjoon] 단어 정렬 (0) | 2021.08.14 |