[백준 자바] 25344번(행성 정렬)

실버 4

문제

행성 정렬은 행성들이 일직선으로 정렬된 것처럼 보이는 현상이다. 최근 지구에서도 18년 만에 행성 정렬을 관측할 수 있었다.

평행세계의 준서가 살고 있는 지구에서는 𝑁$N$개의 행성을 관측할 수 있다. 준서는 얼마나 기다려야 𝑁$N$개의 행성이 일렬로 나열되는 순간을 볼 수 있을지 궁금해졌다.

하늘을 열심히 관찰한 결과, 준서는 다음 사실들을 알 수 있었다.

•  𝑁$N$개의 행성이 일렬로 나열되는 순간이 존재한다.
• 행성 정렬의 주기는 109$10^9$초 이하이다.
•  1,2,3$1, 2, 3$번째 행성은 𝑇1$T_1$초마다 일렬로 나열된다.
•  2,3,4$2, 3, 4$번째 행성은 𝑇2$T_2$초마다 일렬로 나열된다.
• ...
•  𝑁−2,𝑁−1,𝑁$N-2, N-1, N$번째 행성은 𝑇𝑁−2$T_{N-2}$초마다 일렬로 나열된다.

준서를 위해 행성 정렬의 주기를 구해주자.

입력

첫째 줄에 정렬되길 바라는 행성의 개수 𝑁$N$이 주어진다. (3≤𝑁≤100000$3 \leq N \leq 100\,000$)

둘째 줄에 행성이 일렬로 나열되는 주기를 나타내는 정수 𝑇1,𝑇2,⋯,𝑇𝑁−2$T_1, T_2, \cdots, T_{N-2}$가 공백으로 구분되어 주어진다. (1≤𝑇𝑖≤100000$1 \leq T_i \leq 100\,000$)

출력

행성 정렬의 주기를 출력한다. 행성 정렬의 주기는 109$10^9$초 이하이다.

 

---

 

728x90

행성들이 정렬되는 주기는 각 주기의 최소공배수와 같다.

1, 2, 3번째 행성의 정렬 주기가 2이고, 2, 3, 4번째 행성의 정렬 주기가 3이라면 1, 2, 3번째 행성이 정렬되는 시점은 2, 4, 6, ...이고, 2, 3, 4번째 행성이 정렬되는 시점은 3, 6, 9, ...이다. 따라서 1, 2, 3, 4번째 행성이 모두 정렬되는 최소 시점은 두 주기의 최소공배수인 6이다.

 

• 주기들을 배열에 저장한다.
• 배열의 원소들이 최소공배수를 구합니다. 만약 행성의 개수가 3이라면, 주기는 1개이므로 그대로 출력한다.
• 배열의 첫 번째 원소와 두 번째 원소의 최소공배수를 구한다.
• i=3부터 배열의 끝까지 현재 최소공배수와 배열의 i번째 원소의 최소공배수를 구하고 그 값을 갱신한다.
• 최종 최소공배수를 출력한다.

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

public class Main25344 {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());

    if (N == 3) {
      bw.write(br.readLine());
    } else {
      int[] arr = new int[N - 2];

      StringTokenizer st = new StringTokenizer(br.readLine(), " ");
      for (int i = 0; i < N - 2; i++)
        arr[i] = Integer.parseInt(st.nextToken());

      long lcm = lcm(arr[0], arr[1]);
      for (int i = 2; i < N - 2; i++)
        lcm = lcm(lcm, arr[i]);

      bw.write(String.valueOf(lcm));
    }

    bw.flush();
    br.close();
    bw.close();
  }

  public static long lcm(long a, long b) {
    return (a * b) / gcd(a, b);
  }

  public static long gcd(long a, long b) {
    if (b == 0)
      return a;
    else
      return gcd(b, a % b);
  }
}