[Java] 3단계. 분수 합 [1735번]

https://www.acmicpc.net/problem/1735

• 예제 입력1

2 7
3 5

• 예제 출력1

31 35

---

• 문제 접근
  • 입력
    
    • 첫째 줄, 둘째 줄 : 각 분수의 분자와 분모가 주어짐 '분자 분모'
    • 네 자연수는 30,000이하
  • 출력
    
    • 첫째 줄 : 구하고자하는 기약분수의 분자와 분모를 출력
• 문제 해결
  • 분모의 최소공배수를 구함
  • 최소공배수 / 첫째 줄 분모 = A
  • 최소공배수 / 둘째 줄 분모 = B
  • (첫째 줄 분자 * A) + (둘째 줄 분자 * B) = 분자
  • 최소공배수 = 분모
  • 값이 매우 커질 수 있기 때문에 long을 사용
  • 분수를 합치고 나서 분모와 분자가 최대공약수로 나누어야만 기약분수가 성립 됨
    
    • 2/4, 10/25 → 50/100 + 40/100 = 90/100 →  기약분수가 아님
    • 최대공약수 10  : 90 / 10, 100 / 10 → 9/10
• 기존 풀이 [메모리 : 14,204 KB / 시간 : 108 ms]

public static void main(String[] args) throws IOException{
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String[] input = br.readLine().split(" ");
    long childA = Integer.parseInt(input[0]), parentA = Integer.parseInt(input[1]);

    input = br.readLine().split(" ");
    long childB = Integer.parseInt(input[0]), parentB = Integer.parseInt(input[1]);

    long parentRF = lcm(parentA, parentB);
    long childRF = (childA * parentRF / parentA) + (childB * parentRF / parentB);
    long gcd = gcd(parentRF, childRF);

    sb.append(childRF/gcd).append(" ").append(parentRF/gcd);
    System.out.println(sb);
}

private static long gcd(long a, long b){
    return b == 0 ? a : gcd(b, a % b);
}

private static long lcm(long a, long b){
    return a * b / gcd(a, b);
}