[Java] 수열의 순환

1. 문제 설명

1 ~ n 까지 1씩 증가하다가 n에 도착하면 1로 돌아오는 수열이 있다
ex) 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 (n = 5)
여러 수열이 존재한다고 했을 때 모든 수열이 다시 1부터 시작되는 위치는 몇 번째 원소인가?
ex)
1, 2, 3, 1, 2, 3, 1, 2, 3 (n = 3)
1, 2, 1, 2, 1, 2, 1, 2, 1 (n = 2) 답 : 7

입력 형식

첫 줄에는 순환 수열의 수를 나타내는 1이상 10이하의 N이 주어진다.

두 번째 줄에는 각 수열의 순환 주기를 나타내는 자연수 N개가 공백으로 구분되어 주어진다. 순환주기는 1이상 100이하의 자연수이다.

출력 형식

첫 번째 원소를 제외하고 그 이후 최초로 모든 수열이 1이 되는 원소의 번호를 자연수로 출력한다.

2. 문제 접근

순환의 규칙성

• 일정 주기를 두고 반복하는 일들은 동시에 만나는 지점이 항상 존재 (시계 시분초)
• 항상 주기의 배수가 되는 회차 이후에 새롭게 순환 시작
  즉 주기가 일정한 사건들의 발생 시험을 계산할 땐 공배수의 성질 이용
  ex)
  1, 2, 3, 1, 2, 3, 1, 2, 3 (주기 : 3)
  1, 2, 1, 2, 1, 2, 1, 2, 1 (주기 : 2)
  3과 2의 최소공배수 6
  즉 6번째 숫자까지는 만나지 않다가 7번째에 만나게 된다

다만 이 문제는 순환 수열의 수가 10 이하이기 때문에 만약 10이라고 가정하면
10개의 최소공배수를 구해야한다 -> 이는 최소공배수 성질을 이용한다면
만약 3개 최소공배수를 구한다고하면 (A, B, C)
LCM(LCM(A,B), C) < 이와 같다
즉 최소공배수를 구한값에 C를 추가해 이 수의 최소공배수를 구할 수 있다
이를 적용하여 풀어보자

3. 소스코드

import java.util.Scanner;

public class Q4D {
    static Scanner sc = new Scanner(System.in);
    private static long getGlobalPeriod(int n, long[] sizes) {
        return MathUtil.getLCM(sizes);
    }

    public static void main(String[] args) {
        int n = sc.nextInt(); // 수열의 개수
        long[] sizes = new long[n]; // 수열 주기

        for(int i = 0 ; i < n; i++){
            sizes[i] = sc.nextInt();
        }

        long answer = 1 + getGlobalPeriod(n, sizes);

        System.out.println(answer);
    }
}
class MathUtil{
    public static long getLCM(long[] numbers){
        if(numbers.length == 0){ // 들어오는 배열의 수가 없다면 0리턴(예외처리)
            return 0;
        }
        long lcm = numbers[0]; // 최소공배수를 구해 미리 계산한다
        for(int i = 1; i < numbers.length; i++){
            // lcm := numbers[0] ~ numbers[i - 1]에 대한 최소공배수
            lcm = getLCM(lcm, numbers[i]);
            // lcm := numbers[0] ~ numbers[i]에 대한 최소공배수
        }
        return lcm;
    }
    public static long getLCM(long a, long b){
        return a * b / getGCD(a, b);
    }
    public static long getGCD(long a, long b){
        if(a % b == 0){
            return b;
        }
        return getGCD(b, a % b);
    }
}