풀이
해당 문제는 최대공약수와 최소공배수의 알고리즘 공식을 알면 쉽게 풀 수 있는 문제입니다.
최대공약수 : 두 수 이상의 여러 수의 공통된 최대 약수(약수 : 어떤 수를 나누어떨어지게 하는 수) 최소공배수 : 두 수 이상의 서로 공통으로 존재하는 배수 중 가장 작은 배수(배수 : 어떤 수 끼리 곱한 수) |
최대공약수와 최소공배수를 구하는 수학 풀이를 보면 아래와 같습니다.
하지만 이렇게 나누고 구하면 수가 커질 경우 알고리즘을 작성하는 데 어려움이 발생합니다.
그래서 유클리드 호제법을 이용하면 됩니다.
유클리드 호제법( Euclidean algorithm )이란?
유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나
호제법이란, 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타내는 것으로 명시적으로 기술된 가장 오래된 알고리즘 중 하나이다.
2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수라고 한다. |
위의 방법을 사용하면 아래와 같이 풀이를 할 수 있다.
최대공약수
24 와 18 을 나누었을 때, 나머지가 6이면 해당 나눈 수 18과 나머지를 나누었을 때 나머지가 0으로 나눠지면
두 수의 최대 공약수는 6이다.
두 수의 나머지를 나눈 수에 나눴을 때 0이 된다면 해당 나머지는 최대공약수가 된다.
최소공배수
두 수의 곱했을 때, 해당 값을 구한 최대공약수로 나누게 된 수가 최소 공배수가 된다.
최대공약수만 구하면 해당 알고리즘은 쉽게 풀이되며 계속 0이 될 수 있는 나머지를 구하기 때문에 재귀 알고리즘을 적용해야된다.
코드
package Bronze;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class B_2609 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 두 수 입력 받음
int num1 = Integer.parseInt(st.nextToken());
int num2 = Integer.parseInt(st.nextToken());
int gcd = getGCD(num1, num2);
//최대공약수 출력
System.out.println(gcd);
//최소공배수 출력
System.out.println(((num1*num2)/gcd));
}
//최대공약수를 구하는 메서드
private static int getGCD(int num1, int num2) {
// 나머지가 0이면 return
if (num1%num2 == 0) return num2;
// 아닐 경우 다시 나눔
return getGCD(num2, num1%num2);
}
}
'공부' 카테고리의 다른 글
[ERROR] bootImageBuild 시 open /cnb/buildpacks/... : no such file or directory (0) | 2024.03.27 |
---|---|
[ERROR] 디스크를 WSL2에 연결하지 못했습니다. 지정된 파일을 찾을 수 없습니다.Error code: Wsl/Service/CreateInstance/MountVhd/HCS/ERROR_FILE_NOT_FOUND (0) | 2024.03.24 |
[ERROR] S3 - The bucket does not allow ACLs (1) | 2023.12.05 |
[GITHUB] Repository 명명 규칙 및 이름 변경 (0) | 2023.11.05 |
[ERROR] 블로그 미넴 스킨 수정 - 일부 글짤림 현상 (0) | 2023.09.11 |