JAVA 백준 23276번 Locust Locus

문제

There are two different species of periodical cicadas that only appear from hibernation every $13$ and $17$ years, respectively. Your old grandpa tells you that he saw them simultaneously back in '92. You start pondering how many years you have to wait until you see them again. You collect information about other pairs of periodical cicadas and when they were last observed to find out when the next simultaneous appearance is.
Given several different pairs of cicadas and their last simultaneous appearance, find the next year that one of the pairs reappears.

입력

The first line of input contains a single integer k$k$ (1≤k≤99$1 \le k \le 99$), the number of pairs of periodical cicadas. Then follow k$k$ lines, each containing three integers y$y$, c1$c_1$ and c2$c_2$ (1800≤y≤2021$1800 \le y \le 2021$, 1≤c1,c2≤99$1 \le c_1, c_2 \le 99$), the year this pair was last observed and cycle lengths for the first and second species, respectively. You may assume that none of the k$k$ pairs reappears earlier than 2022$2022$.

3
1992 13 17
1992 14 18
2001 5 7

2
2020 2 3
2019 3 4

출력

Output the first year a pair reappears.

2036

2026

알고리즘 분류

유클리드 호제법(euclidean), 수학(math), 정수론(number_theory)

힌트

동시쌍 매미 출현후 하나가 나타는 다음해를 구하시오
매미쌍 출현 케이스 1<= k <=99
1800<=y<=2021, 1<=c1, c2<=99
2022년 이젠에는 나타나지 않는다고 가정

소스코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int K = scanner.nextInt();
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < K; i++) {
            int y = scanner.nextInt();
            int c1 = scanner.nextInt();
            int c2 = scanner.nextInt();
            int ap = y + LCM(c1, c2);
            if (ans > ap) ans = ap;
        }
        System.out.println(ans);
    }

    // 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);
    }
}