GCD (최대 공약수)
■ 정의
1. 22 x 8 크기의 직사각형을 짧은 변(8)을 한 변으로 하는 정사각형으로 분할
2. 정사각형을 제외한 8 x 6 직사각형을 짧은 변(6)을 한변으로 하는 정사각형으로 분할
3. 남은 6 x 2 직사각형을 2 x 2 크기의 정사각형 3개로 분할
☞ 마지막까지 나누어 떨어진 정사각형의 한 변의 길이가 최대 공약수가 됨
■ Code
import java.util.Scanner;
public class EuclidGCD {
static int gcd(int x, int y){
if(y == 0)
return x;
else
return gcd(y, x % y);
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
System.out.println("두 정수의 최대공약수를 구합니다.");
System.out.print("두 정수를 입력하세요: ");
int x = sc.nextInt(); int y = sc.nextInt();
System.out.println("최대공약수는 " + gcd(x, y) + " 입니다.");
}
}
LCD (최소 공배수)
■ 정의
두 수 A, B의 곱을 GCD로 나누어 주어 계산함
ex) A = 12, B = 6, GCD = 6 일 때, LCD = (12 x 6) / 6 = 12
■ Code (백준 No.1934)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int gcd(int x, int y){
if(y == 0)
return x;
else
return gcd(y, x % y);
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int i = 0; i < T; i++){
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int lcd = (A * B) / gcd(A, B);
System.out.println(lcd);
}
}
}
'Java > TIL (Today I Learned)' 카테고리의 다른 글
[JAVA] 추상클래스 (abstract) / 인터페이스 (interface) (0) | 2023.08.07 |
---|---|
[JAVA] 에라토스테네스의 체 (0) | 2023.03.20 |
[JAVA] contains() / replace() (0) | 2023.02.07 |
[JAVA] StringBuilder (0) | 2023.02.06 |
[JAVA] Overloading / Overriding (0) | 2023.01.30 |
댓글