[백준] 2702: 초6 수학 (Java)

초6 수학

백준 수학 유클리드 호제법 Python Java

문제 분석

• 두 정수 a, b의 최소공배수(LCM)와 최대공약수(GCD) 출력
• 제약: T ≤ 1,000 / a, b ≤ 1,000

접근법

• GCD: 유클리드 호제법 — gcd(a, b) = gcd(b, a mod b)
• LCM: a × b ÷ gcd(a, b)

Tip: LCM 계산 시 a / g * b 순서로 하면 오버플로우 방지 (나눗셈 먼저)

풀이 (Python)

import sys, math
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    a, b = map(int, input().split())
    g = math.gcd(a, b)
    print(a * b // g, g)

풀이 (Java)

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

public class Main {
    static int gcd(int a, int b) {
        while (b != 0) { int t = b; b = a % b; a = t; }
        return a;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int g = gcd(a, b);
            sb.append(a / g * b).append(' ').append(g).append('\n');
        }
        System.out.print(sb);
    }
}

예제 트레이스

a=42, b=56

gcd(42, 56):
  42 % 56 = 42  → gcd(56, 42)
  56 % 42 = 14  → gcd(42, 14)
  42 % 14 = 0   → gcd(14, 0) = 14

lcm = 42 / 14 * 56 = 3 * 56 = 168

출력: 168 14 ✓

시간 복잡도

O(T log min(a,b))

공간 복잡도

O(1)

알고리즘 풀이 블로그