[백준] 1934번 : 최소공배수 - JAVA [자바]

 
www.acmicpc.net/problem/1934

1934번: 최소공배수

 

---

• 문제

 

 

 

 

 

 

바로 직전 문제인 '최대공약수와 최소공배수' 문제를 풀었다면 그리 어렵지 않게 풀 수 있었을 것이다.

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

이 문제는 유클리드 알고리즘으로 풀라고 나온 문제다. 즉, 유클리드 호제법(Euclidean algorithm)을 사용하라는 것인데, 앞서 필자가 이미 '최대공약수와 최소공배수' 문제를 풀이하면서 설명했다.

 

'꼭 아래 포스팅을 먼저 보고 오시길 바란다'

 

http://st-lab.tistory.com/154#알고리즘

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

 

 

 

즉, 두 수가 주어지면 GCD로 최대공약수를 구해준 다음 두 수의 곱에 구했던 최대공약수를 나눠주면 된다.

해당 알고리즘에 대한 설명은 위 링크에서 자세하게 다루고 있으니 반복하여 설명하지는 않겠다.

 

 

간단히 코드로만 보자면 이렇다.

 

main() {
	int a = input();
	int b = input();
			
	int d = gcd(a, b);	// 최대공약수를 구해준다.
			
	print(a * b / d);	// 두 수의 곱을 최대공약수로 나눈다.
			
}

// 최대공약수 반복문 방식
public static int gcd(int a, int b) {
 
	while (b != 0) {
		int r = a % b; // 나머지를 구해준다.
 
		// GCD(a, b) = GCD(b, r)이므로 변환한다.
		a = b;
		b = r;
	}
	return a;
}

 

 

이를 토대로 이제 출력과 몇 가지 소스만 만들어주면 된다.

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

이전 포스팅과 여타 다를 바 없이 아래와 같이 2가지 입력 방법을 통해 성능을 비교해보려한다. 이렇게 반복적으로 출력해야하는 문제들은 한 번에 묶어서 출력해주는 것이 훨씬 좋아 굳이 매 번 println() 으로 반복출력 해줄 필요가 없기 때문에...

 

출력은 모두 StringBuilder 로 통일하여 입력방법만 달리하여 풀이하겠다.

 

1 . Scanner

2. BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
        
		StringBuilder sb = new StringBuilder();

		
		for(int i = 0; i < N; i++) {
			
			int a = in.nextInt();
			int b = in.nextInt();
			
			int d = gcd(a, b);	// 최소 공배수 구하기
			
			sb.append(a * b / d).append('\n');
		}
		System.out.println(sb);
		
	}
    
    
	// 최대공약수 반복문 방식
	public static int gcd(int a, int b) {
 
		while (b != 0) {
			int r = a % b; // 나머지를 구해준다.
 
			// GCD(a, b) = GCD(b, r)이므로 변환한다.
			a = b;
			b = r;
		}
		return a;
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

유클리드 호제법은 보통 알고리즘 문제 중 수학 부문에서 대표적인 문제다. 그러니 최대공약수를 구하는 방법과, 이를 이용한 최소공배수를 구하는 방법 정도는 외워두는 것이 좋다.

 

 

 

---

- 방법 2 : [BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st;
		
		for(int i = 0; i < N; i++) {
			
			st = new StringTokenizer(br.readLine(), " ");
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			int d = gcd(a, b);
			
			sb.append(a * b / d).append('\n');
		}
		System.out.println(sb);

	}
    
    
	// 최대공약수 반복문 방식
	public static int gcd(int a, int b) {
 
		while (b != 0) {
			int r = a % b; // 나머지를 구해준다.
 
			// GCD(a, b) = GCD(b, r)이므로 변환한다.
			a = b;
			b = r;
		}
		return a;
	}
}

 

 

 

크게 어려울 것은 없을 것이다. 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

 

채점 번호 : 25338313  -  방법 2 : BufferedReader

채점 번호 : 25338310  -  방법 1 : Scanner

 

 

 

---

• 정리

 

보통 최대공약수, 최소공배수를 구하는 문제의 경우 대부분이 유클리드 호제법을 사용하여 풀이하기 때문에 이미 다뤘던 내용이라 크게 설명할 것이 없었다.

 

이 번에 정수론 및 조합론이라는 카테고리로 바뀌고 몇 문제가 업데이트 되면서 새로 추가된 문제인데(2020. 1. 1 기준) 이 문제가 없었을 때 직전 문제에서 유클리드 호제법에 대해 자세하게 다뤘던지라..

그리고 함수만 외울 것이 아니라 반드시 원리도 이해하도록 하자. 생각보다 함수는 외우는 사람은 많아도 왜 이렇게 되는지는 모르는 사람이 꽤 있는 것 같다.

 

이왕 푸는 겸 지식을 더하면 좋지 않겠는가?

만약 어렵거나 이해가 되지 않은 부분이 있다면 언제든 댓글 남겨주시면 최대한 빠르게 답변드리겠다.