문제: https://www.acmicpc.net/problem/13241
13241번: 최소공배수
정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 예: 10은 5의 배수이다 (5*2 = 10) 10은 10의 배수이다(10*1 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1, 2, 4,5,10,20의 배수이다. 다
www.acmicpc.net
1. 코드
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long a = sc.nextLong();
long b = sc.nextLong();
long c = gcd(Math.max(a, b), Math.min(a, b));
System.out.println(a * b / c);
}
private static long gcd(long a, long b) {
if(b == 0) return a;
return gcd(b, a % b);
}
}2. 설명
유클리드 호제법을 이용하여 문제를 해결해야만 한다. 그 이외의 방법은 소용이 없었다.
3. 정리
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95
유클리드 호제법 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란
ko.wikipedia.org
https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95
유클리드 호제법 - 나무위키
손으로 계산할 때는 제수와 피제수의 값 크기를 비교해서 적절하게 배열하지만 수식이나 코드로 나타낼 때는 신경쓰지 않아도 되는데, a일 때 a mod b ≡ a(a%b==a)이므로 Gcd(a,b)는 Gcd(b,a)를 호출한다
namu.wiki
'컴퓨터 > 백준 알고리즘' 카테고리의 다른 글
| 백준 알고리즘 - 2485번: 가로수 [Java] (0) | 2023.09.21 |
|---|---|
| 백준 알고리즘 - 1735번: 분수 합 [Java] (0) | 2023.09.20 |
| 백준 알고리즘 - 11478번: 서로 다른 부분 문자열의 개수 [Java] (0) | 2023.09.17 |
| 백준 알고리즘 - 1764번: 듣보잡 [Java] (0) | 2023.09.16 |
| 백준 알고리즘 - 1269번: 대칭 차집합 [Java] (0) | 2023.09.15 |