백준[2485]번 : 가로수 ( JAVA )

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

2485번: 가로수

---

개발환경은 eclipse를 사용했습니다.

 

Code

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

public class Main
{
    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 심어져 있는 가로수의 개수

        int[] arr = new int[n]; 

        for(int i=0;i<n;i++){ // 가로수 위치 입력받음
            arr[i] = sc.nextInt();
        }

        int[] NewArr = new int[n-1];

        int N = n;

        for(int i=n-2;i>=0;i--){ // 가로수들의 위치의 차를 저장

            NewArr[i] = arr[N-1] - arr[N-2];
            N--;
        }

        int ans = 0;

        for(int i=0;i<n-2;i++){ // 유클리드 호제법 사용
            int result = eucd(NewArr[i+1],NewArr[i]); // 최대공약수

            ans = result;

            NewArr[i+1] = ans;
        }

        int count = 1;

        for(int i=arr[0];i<arr[arr.length-1];){ // 전체 심는 개수
            i+=ans;
            count++;
        }

        int answer = count - arr.length; // 전체에서 심어져 있는 개수를 빼준다

        System.out.println(answer);

        sc.close();
    }
    static int eucd(int bn, int sn) // 유클리드 호제법 사용
    {
        int r = bn % sn;
        
        if (r == 0) {
            return sn;
        } else {
            return eucd(sn, r);
        }
    }
}

---

이전 문제들에서 계속 사용되었던 유클리드 호제법을 사용해서 풀었다.

 

코드의 주석을 보면 쉽게 이해할 수 있을 것이다.