https://www.acmicpc.net/problem/1735
문제
> 분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다.
> A와 B는 모두 자연수라고 하자.
> 두 분수의 합 또한 분수로 표현할 수 있다.
> 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오.
> 기약분수란 더 이상 약분되지 않는 분수를 의미한다.접근
수학에서 두 분수의 합을 구하는 방법을 그대로 구현한다.
합이 된 분수의 분모는 두 분수의 최소공배수가 되고,
분자는 각 분모가 최소공배수가 되기위해 곱했던 수를 각각 곱해준 뒤 더한 수이다.
이제 계산된 분자, 분모의 최대공약수를 구해 각각 나눠 기약분수로 만들어주면된다.
문제해결
> 첫 분수의 분자 분모를 A1, B1으로, 두 번째 분수는 A2, B2로 입력받는다.
> 두 분수의 합이 되는 분수의 분모는 rstB로 두 분수의 공배수를 구한다.
> 분자는 각각 서로의 분모를 곱하고 더해서 구한다.
> 기약분수로 만들기 위해 분자와 분모의 최대공약수를 구하는 연산을 한다.
> 분자 분모를 구한 최대공약수로 각각 나눠 기약분수로 만들어 출력한다.
> 최대공약수를 구하기 위해선 gcd 메소드에서 유클리드 호제법을 사용한다.
> 인자로 받은 A와 B에 대해 A를 B로 나눈 나머지 r에 대해서 r이 0이 될 때 까지 나머지로 나누는 수를 계속 나눈다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//1735번 분수 합
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int gcd(int A, int B) {
int a = A, b = B, r;
while(b > 0) {
r = a % b;
a = b;
b = r;
}
return a;
}
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
int A1 = Integer.parseInt(st.nextToken());
int B1 = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int A2 = Integer.parseInt(st.nextToken());
int B2 = Integer.parseInt(st.nextToken());
int rstB = B1 * B2;
int rstA = A1 * B2 + A2 * B1;
int rstAB = gcd(rstA, rstB);
sb.append(rstA / rstAB).append(' ').append(rstB / rstAB);
System.out.print(sb);
}
}
후기
식은 맞고, 최악의 경우도 3만x3만이라 9억까지라 int로도 되는데 틀렸다.
처음엔 분모도 서로 gcd연산으로 최소 공배수를 구한 뒤, 각각 최소공배수가 되기 위한 수를 분자에도 곱해 더해준뒤, 기약분수화 해줬다.
해당 과정에서 중간계산에서 오버플로우가 발생할 수 도 있다고 한다.
그걸 생각해서 최소공배수로 구하지않아도 나중에 기약분수로 나눠 줄 때, 어차피 같아지니까 그냥 최소공배수를 찾지 않고 단순히 분모들을 곱하고 분자도 각각을 곱해줬다.
이렇게 하면 분모, 분자도 최대 9억까지라 안전하다.
