백준 2485 가로수 자바

가로수 문제 보러가기

문제 설명

자바 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;

public class Main {
    static int[] tree;
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        tree=new int[N];
        for(int i=0;i<N;i++){
            tree[i]=Integer.parseInt(br.readLine());
        }
        Arrays.sort(tree);
        int gcd=0;
        for(int i=0;i<N-1;i++){
            int distance=tree[i+1]-tree[i];
            gcd = GCD(distance,gcd);
        }
        System.out.println((tree[N-1]-tree[0])/gcd+1-(tree.length));

    }

    static int GCD(int a, int b)
    {
        if(b==0)return a;
        else return GCD(b,a%b);
    }
}

문제 풀이

일정한 간격이 되도록 하는 가로수의 최소수를 구하려면 가로수 간격들 중에서 최대 공약수를 찾아야합니다.

간격이 일정하면서 간격은 최대한 커야 된다 라는 조건이 있기 때문이죠.

그 다음에 이미 심어져있는 가로수의 위치중 (최대위치-최소위치)/최대공약수+1 은 전체 가로수의 수이며 이미 심어져있는 가로수만 빼면 결과값이 나옵니다.

• 각 가로수 간격을 구한다.
• 간격들 중에 최대 공약수를 찾는다
• 전체 가로수의 수는 (최대위치-최소위치)/최대공약수+1 이다.
• 전체 가로수에서 심어져 있는 가로수만 빼서 결과를 구한다.