[백준 13241번 최소공배수]

 

오늘의 문제는 최소공배수이다.

 

 

처음엔 무조건 완전탐색!

 

완전 탐색이야 당연히 두 수 모두에게 나누어지는 수가 나올 때까지 1씩 더하는 방법이겠지만

이를 최적화하기 위한 방법을 한번 고민해 보았다.

나의 결론은

 

무작위 두 수 a, b의 곱 / (중복되는 수 = 최대공약수)라고 생각하였다.

 

그래서 두 수를 "유클리드 호제법"을 통하여 최대공약수를 구해주고

(a * b) / 최대공약수 로 답을 도출해 보았다.

 

코드는 다음과 같다.

( 코드가 너무 커보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )

( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )

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());
        long A = Long.parseLong(st.nextToken()); // 가장 처음의 A
        long B = Long.parseLong(st.nextToken()); // 가장 처음의 B
        long a = A; // 곧 바뀔 a
        long b = B; // 곧 바뀔 b

        long num = 0; // 최대공약수를 담아줄 num
        long temp = 0; // 수 스왑을 위한 temp
        if(b > a){ // a가 더 크게 세팅하기위한 if문
            temp = a;
            a = b;
            b = temp;
        }

        while(true){ // 유클리드 호제법 구현 !
            if(a % b == 0){
                num = b;
                break;
            }else{
                temp = a % b;
                a = b;
                b = temp;
            }
        }

        System.out.println(A * B / num); // 출력
    }
}

 

 

궁금한 점이 있거나 보충할 점이 있다면 언제든 댓글 부탁드립니다 ~

 

https://www.acmicpc.net/problem/13241