

처음엔 이렇게 풀었는데 특정 입력에서는 통하지 않아서 오답처리가 됐다.
import java.io.*; import java.util.*; 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 A = Integer.parseInt(st.nextToken()); int B = Integer.parseInt(st.nextToken()); int GCD = 1, LCM = 1; while(true){ if((A%2==0)&&(B%2==0)){ A /= 2; B /= 2; GCD *= 2; } if((A%3==0)&&(B%3==0)){ A /= 3; B /= 3; GCD *= 3; } if(!(((A%3==0)&&(B%3==0))||(A%2==0)&&(B%2==0))){ LCM = GCD*A*B; break; } } System.out.println(GCD); System.out.println(LCM); } }
그리고 이 포스트를 참고해서 다시 풀어봤다.
https://st-lab.tistory.com/154
[백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바]
www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 알
st-lab.tistory.com
짧게 요약하자면 숫자 A와 B가 있고, r을 A % B라고 했을 때 ( A >= B )
최대공약수 GCD(A,B) = GCD(B,r)이라는 것이다.
그리고 A = ad, B = bd (a와 b는 서로소이고, d는 A와 B의 최대공약수)라고 했을 때
A와 B의 최소공배수는 a*b*d이다.
따라서 A와 B가 주어지고 둘의 최대공약수인 d를 구한다면
A*B = a*d*b*d 이니 이것을 d로 나눠주면 최소공배수를 구할 수 있다.
import java.io.*; import java.util.*; 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 A = Integer.parseInt(st.nextToken()); int B = Integer.parseInt(st.nextToken()); int d = gcd(A,B); System.out.println(d); System.out.println(A*B/d); } public static int gcd(int a, int b){ while(b!=0){ int r = a%b; a = b; b = r; } return a; } }
'Algorithm > [BOJ] - JAVA' 카테고리의 다른 글
[백준] 1850 : 최대공약수 JAVA 풀이 (1) | 2022.09.30 |
---|---|
[백준] 1934 : 최소공배수 JAVA 풀이 (0) | 2022.09.29 |
[백준] 10799 : 쇠막대기 JAVA 풀이 (0) | 2022.09.29 |
[백준] 10845 : 큐 JAVA 풀이 (0) | 2022.09.19 |
[백준] 9012 : 괄호 JAVA 풀이 (0) | 2022.09.19 |