[Baekjoon] 2436_공약수

Gold V

문제(출처: https://www.acmicpc.net/problem/2436)

---

< 공약수 >

 

문제 풀이 

 

최대 공약수는 C, 최소 공배수는  CxDxE이다.

최대 공약수와 최소 공배수가 주어지고 A와 B를 찾는 것이 문제이므로 D와 E를 구하면 된다.

D와 E를 구하는 방법은 먼저 ( 최소 공배수 / 최대 공약수 )를 구하면 DxE 값을 알 수 있다.

D와 E는 ( 최소 공배수/최대 공약수) 이므로 D와 E 사이에 최대 공약수가 1이어야 한다. 

 

 

 my solution (Java)

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

public class _2436_ { // 공약수

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());

		int max = b / a;
		int result = Integer.MAX_VALUE;
		int num1 = 0, num2 = 0;

		for (int i = 1; i <= max; i++) {
			if (max % i == 0 && result > i + (max / i) && gcd(i, max / i) == 1) {
				result = i + (max / i);
				num1 = i;
				num2 = max / i;
			}
		}
		bw.write((num1 * a) + " " + (num2 * a));
		bw.flush();
	}

	private static int gcd(int i, int j) {
		if (j == 0) {
			return i;
		}
		return gcd(j, i % j);
	}
}

변수)
a, b : 최대공약수, 최소공배수
max : 최소공배수/최대공약수
result : 두 자연수 합 최솟값
num1, num2 : 두 자연수

 

최대공약수와 최소 공배수를 입력받는다. 위에서 말한 것과 같이 D와 E를 구하기 위해 (최소 공배수/최대 공약수) 값을 구한다. 곱해서 (최소 공배수/최대 공약수)  이 값을 만들 수 있는 두 개의 자연수를 구한다. 구한 두 자연수의 합이 앞에서 구한 값보다 작고 두 자연수의 최대 공약수 값이 1이라면 result, num1, num2 값을 업데이트한다.

 

최종 두 자연수를 출력한다.

 

gcd(Integer a, Integer b)

1) b가 0이면 a를 반환한다.

2) gcd(b, a% b)를 호출한다.

---

---