[JAVA] 백준 2609번: 최대공약수와 최소공배수

백준

[JAVA] 백준 2609번: 최대공약수와 최소공배수

스파게티 코더 2024. 7. 12. 15:52

문제

두 개의 자연수가 입력될 때 최대 공약수와 최소 공배수를 출력하는 문제.

아이디어

유클리드 호제법을 사용해 최대 공약수를 구하고 이를 통해 최소 공배수를 구한다.
N, M 중 하나로 다른 자연수가 나누어 떨어질 때까지 그 나머지로 값을 갱신해가며 계산한다.
32와 24라 가정했을 때
- 32 % 24 = 8, 나누어 떨어지지 않았으므로 나머지로 다시 나눗셈 시행
- 24 % 8 = 0, 8로 나누어 떨어졌으므로 최대 공약수는 8
최소 공배수는 32 x 24 / 8의 값인 96이 된다.

풀이

import java.util.*;
import java.io.*;

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 N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 최소 공배수, 최대 공약수를 담을 변수 선언
        int lcm = 0;
        int gcd = 0;

        // 최소 공배수를 구하기 위해 N*M 값을 미리 저장
        int num = N*M;

        while(true) {
            // N이 M으로 나누어 떨어질 때까지 연산 반복
            // 최대 공배수를 구했을 때, N*M / gcd 연산을 통해 최소 공배수 도출
            if(N % M == 0) {
                gcd = M;
                lcm = num / gcd;
                break;
            }
            // 나머지를 M으로, N은 원래 M으로 치환
            else{
                int tmp = M;
                M = N % M;
                N = tmp;
            }
        }

        System.out.println(gcd);
        System.out.println(lcm);
    }
}

채점 결과

기타

셈을 해보면 굳이 작은 수로 큰 수를 나눌 필요가 없다는 사실을 알 수 있다.

문제 링크

2609번: 최대공약수와 최소공배수 (acmicpc.net)