밍의 기록들😉

[문제] 가로수 2485번 본문

자료구조, 알고리즘/문제풀이

[문제] 가로수 2485번

민쓰 2018. 8. 16. 19:19

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


public class StreeTree {

	public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int [] array = new int[n];
        int [] distance = new int[n];
        for(int i=0; i<n; i++){
        	array[i]= scan.nextInt();
        }
        for(int i=0; i<=n-2; i++){
        	distance[i]= array[i+1] - array[i];
        }
       for(int i=0; i<=n-2; i++){
    	   distance[i+1]= gcd(distance[i], distance[i+1]);
       }
       int interval = distance[n-2];
       int streetTree = ((array[n-1]-array[0])/interval)-(array.length-1);
       System.out.println(streetTree); // (마지막수 - 처음수 / interval) - existing tree 
	}

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

'자료구조, 알고리즘 > 문제풀이' 카테고리의 다른 글

[문제] 웜바이러스 2606번  (0) 2018.09.05
[문제] 이진 패턴  (0) 2018.09.04
[문제] 자연수의 분할  (4) 2018.09.04
[문제] 단지번호 붙이기 2667번  (0) 2018.08.27
[문제] 분수 합 1735번  (0) 2018.08.16
[문제] 가로수 2485번  (0) 2018.08.16
0 Comments
댓글쓰기 폼