알고리즘/백준

[BAEKJOON]13241 최소공배수

응애~ 개발자 2025. 5. 8. 22:53
728x90
반응형

문제 요약

문제풀이

 이번 문제는 최대 공배수이다. 여러 가지 푸는 방법이 있지만 최적화로는 유클리드 호제법이라 최적의 방식이 있다 아래 글보고 바로 따라하면 푸는 데는 지장이 없다. 코드 설명은 아래 글만 봐도 이해하는데는 문제가 없다고 생각한다.

https://jih3508.tistory.com/13

 

유클리드 호제법(Euclidean algorithm)

이론1. 유클리드 호제법이란?두 개의 정수 혹은 다수의 자연수에서 최대공약수를 구하는 알고리즘이다. 원리는 두 수가 서로 나눠서 나머지를 구한다. 만약 나머지가 0이면 그 수가 최대 공약수

jih3508.tistory.com

 

Code

Python

def GCD(x, y):
    while x % y != 0:
        r = x % y
        x, y = y, r
    return y

def LCM(x, y):
    return x * y // GCD(x, y)

A, B = map(int, input().split())
print(LCM(A, B))

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
		long A = Integer.parseInt(st.nextToken());
		long B = Integer.parseInt(st.nextToken());

		System.out.println(LCM(A,B));

	}

	public static long GCD(long x, long y) {
		long r;
		while(x % y != 0) {
			r = x  % y;
			x = y;
			y = r;
		}
		return y;
	}

	public static long LCM(long x, long y) {
		return x * y / GCD(x, y);
	}


}

Javascript

var input = require('fs').readFileSync("/dev/stdin", "utf-8").toString().trim().split(" ");

const GCD = (x, y) =>{
    let r;
    while(x % y != 0){

        r = x % y;
        x = y;
        y = r;
    }
    return y;
}

const LCM = (x, y) =>{
    return x * y / GCD(x, y);
}

const [A, B] = input.map(x => parseInt(x));
console.log(LCM(A, B));
728x90
반응형