[백준 2485] 가로수 (Java)

https://www.acmicpc.net/problem/2485

2485번: 가로수

접근 방식

주어진 가로수의 간격 간의 최대공약수 == 최종 간격

 

최대 공약수는 유클리드 호제법을 사용하였다.

 

간격을 담은 배열을 만들어 주어진 가로수 간의 간격을 담고

앞에서부터 그 다음 값과 차례로 최대 공약수를 구해나갔다.

 

 

소스 코드

import java.util.Scanner;

public class Main {
    private static int[] gaps;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int[] trees = new int[N];
        gaps = new int[N - 1];

        for (int i = 0; i < N; i++) {
            trees[i] = scanner.nextInt();

            if (i > 0) {
                gaps[i - 1] = trees[i] - trees[i - 1];
            }
        }

        for (int i = 0; i <= gaps.length - 2; i++) {
            gaps[i + 1] = gcd(gaps[i], gaps[i + 1]);
        }

        int gap = gaps[gaps.length - 1];

        System.out.println((trees[N - 1] - trees[0]) / gap - (N - 1));
    }

    private static int gcd(int a, int b) {
        while (b > 0)
        {
            int tmp = a;

            a = b;
            b = tmp%b;
        }
        return a;
    }
}