[백준][Java] 1735번 분수 합

안녕하세요 :)

적어도 하루 1개 이상 알고리즘 문제를 해결하려 노력하고 있습니다.

혼자 해결 가능한 문제도 있고, 어려웠던 문제도 있던 차라 복습하고자  글을 써 내려갑니다.

 

---

 

백준 1735 분수 합

오늘 문제는 두 개의 분수가 주어졌을때, 이 둘의 합을 기약분수 형태로 출력하는 문제입니다.

 

📘 문제

 

💡 해결 방법

입력받은 두 분수의 분모를 기준으로 최소공배수(LCM)를 구해 공통 분모를 만든 후,

각각의 분자를 공통 분모에 맞춰 조정한 뒤 더합니다.

합쳐진 분수의 최대공약수(GCD)를 구해서 기약분수로 만들어 출력합니다.

더 자세히 GCD와 LCM에 알고 싶다면 아래 링크를 통해 확인해 주세요.

[백준][Java] 1934번 최소공배수

 

✅ 풀이 및 설명 (설명은 더보기 클릭)

• 두 개의 분수를 각가 a, b, c, d 형태롤 입력받습니다.
• 두 분수의 분모를 통일하기 위해 getLCM() 함수를 통해 최소공배수를 구합니다.
• 각각의 분자를 공통 분모에 맞춰 변환 후 각 분자를 더해줍니다.
• 분자와 분모를 getGCD()함수를 통해 최대공약수로 나누어 기약분수 형태로 만듭니다

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

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

        // 첫 번째 분수: a / b
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        // 두 번째 분수: c / d
        st = new StringTokenizer(br.readLine());
        int c = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());

        // 공통 분모
        int commonDenominator = getLCM(b, d);

        // 통분한 뒤의 분자
        int molecule = a * (commonDenominator / b) + c * (commonDenominator / d);

        // 기약분수로 만들기
        int gcd = getGCD(molecule, commonDenominator);
        molecule /= gcd;
        commonDenominator /= gcd;

        // 결과 출력
        System.out.println(molecule + " " + commonDenominator);

        br.close();
    }

    // 최대공약수
    private static int getGCD(int x, int y) {
        if (y == 0) return x;
        return getGCD(y, x % y);
    }

    // 최소공배수
    private static int getLCM(int x, int y) {
        return x * y / getGCD(x, y);
    }
}

 

처음엔 단순히 분수를 더하면 되는 줄 알았는데, 기약분수로 출력해야 해서 LCM과 GCD 개념이 함께 필요했습니다.

getGCD()와 getLCM() 개념만 잘 알면 앞으로 아주 유용하게 사용할 것 같습니다.

 

---

공부하면서 유용했던 부분 메모 겸 공유하고자 끄적입니다.

고쳐야 하는 부분 있다면 댓글 남겨주시면 수정하겠습니다.

행복한 하루 보내세요 (❁´◡`❁)