[JAVA 38일차 / 하루 3문제] 13241번,

1. 13241번 최소공배수

import java.io.*;
import java.util.StringTokenizer;

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

        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());

        long gcd = gcd(A, B);
        long lcm = (A / gcd) * B; // 오버플로우 방지

        System.out.println(lcm);
    }

    // 유클리드 호제법을 이용한 GCD 계산
    public static long gcd(long a, long b) {
        while (b != 0) {
            long temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}

• 이 또한 유클리드 호제법을 알아야 한다.

---

2. 1735번 분수 합

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        int c = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());

        // [1] 분수 덧셈
        int numerator = a * d + c * b;  // 새로운 분자
        int denominator = b * d;        // 새로운 분모

        // [2] 최대공약수(GCD) 계산
        int gcd = gcd(numerator, denominator);

        // [3] 기약 분수 출력
        System.out.println((numerator / gcd) + " " + (denominator / gcd));
    }

    // 유클리드 호제법을 이용한 최대공약수(GCD) 계산
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}

---

3. 2485번 가로수

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 가로수 개수
        int[] trees = new int[N];

        for (int i = 0; i < N; i++) {
            trees[i] = Integer.parseInt(br.readLine());
        }

        // [1] 가로수 간격 구하기
        int[] gaps = new int[N - 1];
        for (int i = 0; i < N - 1; i++) {
            gaps[i] = trees[i + 1] - trees[i];
        }

        // [2] 모든 간격의 GCD 구하기
        int gcdValue = gaps[0];
        for (int i = 1; i < gaps.length; i++) {
            gcdValue = gcd(gcdValue, gaps[i]);
        }

        // [3] 추가로 심어야 할 나무 개수 계산
        int additionalTrees = 0;
        for (int gap : gaps) {
            additionalTrees += (gap / gcdValue) - 1;
        }

        System.out.println(additionalTrees);
    }

    // 유클리드 호제법을 이용한 GCD 계산
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}