[Baekjoon] 2942_퍼거슨과 사과

Silver II

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

---

< 퍼거슨과 사과 >

 

문제 풀이 

 

빨간 사과와 초록 사과의 최대공약수를 구한 후 최대 공약수의 약수를 구한다. 

 

 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 _2942_ { // 퍼거슨과 사과

	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 r = Integer.parseInt(st.nextToken());
		int g = Integer.parseInt(st.nextToken());

		int num = gcd(r, g);

		for (int i = 1; i <= Math.sqrt(num); i++) {
			if (num % i == 0) {
				bw.write(i + " " + r / i + " " + g / i + "\n");
				if (num / i != i)
					bw.write(num / i + " " + r / (num / i) + " " + g / (num / i) + "\n");
			}
		}
		bw.flush();
	}

	private static int gcd(int r, int g) {
		if (g == 0) {
			return r;
		}
		return gcd(g, r % g);
	}
}

변수)
r, g : 빨간 사과, 초록 사과
num : 최대공약수

 

빨간 사과와 초록 사과를 입력받는다. gcd 함수를 호출하여 빨간 사과와 초록 사과의 최대 공약수를 구한다. 1부터 최대 공약수의 제곱근까지 탐색하며 최대 공약수의 약수인지 판단한다. 약수라면 그 값과 빨간 사과와 초록 사과를 약수로 나눈 값을 출력한다. 

 

gcd (int r , int g)

g가 0일 경우 r을 반환한다.

gcd(g, r%g)를 반환한다. 

---

---