[백준] 2485 : 가로수

문제 출처: https://www.acmicpc.net/problem/2485

---

문제

---

시도

// 가로수 수: N (3 ~ 100,000)
// 가로수 위치: x ( ~ 1,000,000,000)

// 방정식? -> f(n) = a*(n-1) + b

// 방정식 사용 시 b는 무조건 첫 번째로 주어진 가로수 위치

// 이후 가로수 위치를 받을 때마다 자신 바로 이전의 가로수 위치와의 거리를 계산
// 가장 최소 차이를 보이는 거리를 증가 기준점 a로 삼고, a가 1이 될 때까지 1씩 빼기

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        int min = Integer.MAX_VALUE;
        arr[0] = Integer.parseInt(br.readLine());
        for(int i = 1; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            if(min > arr[i] - arr[i-1]) min = arr[i] - arr[i-1];
        }

        for(int i = min; i >= 1; i--) {

            boolean check = false;
            for(int j = 0; j < N; j++) {
                if((arr[j] - arr[0]) % i != 0) {
                    check = true;
                    break;
                }
            }
            if(!check) {
                System.out.print((arr[N-1] - arr[0])/i - N + 1);
                break;
            }
        }
    }
}

등차수열의 방정식 f(n) = a * (n-1) + b를 적용하여 풀었다.

---

풀이

 

다른 사람의 풀이를 참고하니 각 가로수 사이의 길이에 대한 최대공약수를 구하여 그걸 바탕으로 등차수열 방정식을 적용하는 걸 확인했다.

 

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        int gcd = 0;
        for(int j=1; j<n; j++) {
            int value = arr[j] - arr[j-1];
            gcd = gcd(value, gcd);
        }
        
        int answer = (arr[arr.length-1]-arr[0])/gcd +1;
        System.out.print(answer - arr.length);
	}
    
    static int gcd(int x, int y) {
        int max = Math.max(x, y);
        int min = Math.min(x, y);
        
        while(min>0) {
            int tmp = max;
            max = min;
            min = tmp % min;
        }
        
        return max;
    }
}

풀이 참고: https://www.acmicpc.net/source/68511844

---

알게 된 점

 

- 여기서 최대 공약수를 찾아야 겠다는 발상은 어디서 나온건지 궁금하다..