1934번: 최소공배수
두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있
www.acmicpc.net
☕Language: Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
for(int i=0; i<n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int max = 0;
for(int j=1; j<=45000; j++) {
if(a % j ==0 && b % j == 0) {
max = Math.max(max, j);
}
}
long result = (a/max) * (b/max) * max;
bw.write(result+"\n");
}
bw.flush();
}
}
|
🤔 해설
1. for(int j=1; j<=45000; j++)
- 최대값 45,000
2. if(a % j ==0 && b % j == 0)
- 공약수 탐색
3. max = Math.max(max, j);
- 최대공약수 탐색
4. long result = (a/max) * (b/max) * max;
- 최소공배수 공식
- 자료값 타입 유의
😮 이 외의 풀이
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
StringTokenizer st;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
sb.append(lcm(a, b)).append('\n');
}
br.close();
bw.write(sb.toString());
bw.flush();
bw.close();
}
// 최대공약수 재귀 방식
public static int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
// 최소공배수 : Least Common mulitple
public static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
}
|
유클리드 호제법 - 재귀
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
StringTokenizer st;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
sb.append(lcm(a, b)).append('\n');
}
br.close();
bw.write(sb.toString());
bw.flush();
bw.close();
}
// 최대공약수 반복문 방식
public static int gcd(int a, int b) {
while(b!=0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
// 최소공배수 : Least Common Mulitiple
public static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
}
|
유클리드 호제법 - 반복문
🔗 소스 코드
GitHub
📚 참고 자료
[백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바]
www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 알
st-lab.tistory.com
'Computer > Algorithm_Java' 카테고리의 다른 글
| [Algorithm_Java] 10872번 팩토리얼 (Success) (0) | 2023.10.01 |
|---|---|
| [BaekJoon] 11866번 요세푸스 문제 0 문제 풀이 (Success) (0) | 2023.09.30 |
| [BaekJoon] 11478번 서로 다른 부분 문자열의 개수 문제 풀이 (Success) (0) | 2023.09.28 |
| [BaekJoon] 15651번 N과 M (3) 문제 풀이 (Success) (0) | 2023.09.26 |
| [BaekJoon] 13909번 창문 닫기 문제 풀이 (Success) (0) | 2023.09.23 |
