🌞Algorithm/🔥Baekjoon
[Baekjoon] 2942_퍼거슨과 사과
뿌야._.
2024. 5. 20. 10:51
문제(출처: 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)를 반환한다.