JAVA 백준 21412번 Дробь

문제

Коля учится в третьем классе, сейчас они проходят простые дроби с натуральными числителем и знаменателем. Вчера на уроке Коля узнал, что дробь называется правильной, если ее числитель меньше знаменателя, и несократимой, если нет равной ей дроби с меньшими натуральными числителем и знаменателем.
Коля очень любит математику, поэтому дома он долго экспериментировал, придумывая и решая разные задачки с правильными несократимыми дробями. Одну из этих задач Коля предлагает решить вам с помощью компьютера.
Найдите наибольшую правильную несократимую дробь, у которой сумма числителя и знаменателя равна n.

입력

Во входном файле записано одно целое число n (3<= n<= 1000).

10
23

출력

Выведите в выходной файл числитель и знаменатель искомой дроби.

3 7
11 12

알고리즘 분류

브루트포스 알고리즘(bruteforcing), 유클리드 호제법(euclidean), 수학(math), 정수론(number_theory)

힌트

분자가 분모보다 작은수를 분수라 한다
정수 n이 주어였을때 n (3<= n<= 1000)
가장 큰 분수를 구한다

소스코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = n / 2 + 1; i < n; i++) {
            int gcd = GCD(i, n - i);
            if (gcd == 1) {
                System.out.println(n - i + " " + i);
                break;
            }
        }
    }

    // greatest common divisor
    static int GCD(int a, int b) {
        if (b == 0) return a;
        return GCD(b, a % b);
    }

    // least common multiple (a*b/GCD(a,b)) oerverflow
    static int LCM(int a, int b) {
        return (a * b) / GCD(a, b);
    }
}