백준 2485번: 가로수

문제

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

---

코드

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    List<Integer> differences = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    int preValue = 0;

    int n = Integer.parseInt(br.readLine());
    while (n-- > 0) {
        int input = Integer.parseInt(br.readLine());
        list.add(input);

        if (preValue != 0) {
            differences.add(Math.abs(preValue - input));
        }

        preValue = input;
    }

    Collections.sort(list);

    int gcd = Integer.MAX_VALUE;
    for (int i = 1; i < differences.size(); i++) {
        int temp = gcd(differences.get(i-1), differences.get(i));
        gcd = temp > gcd ? gcd : temp;
    }

    int answer = 0;
    int pre = list.get(0);
    for (int i = 1; i < list.size(); i++) {
        if (list.get(i) - pre != gcd) {
            answer += ((list.get(i) - pre) / gcd) - 1;
        }
        pre = list.get(i);
    }

    System.out.println(answer);
}

private static int gcd(int a, int b) {
    return b!=0 ? gcd(b, a%b) : a;
}

---

흐름

1. 입력 받은 값들을 뺀 값의 차를 구한 값으로 약수를 구하기 위한 differences,
   입력 받은 값을 그대로 저장하는 list 변수 생성.
2. 두 리스트 모두 n 만큼 돌면서 값을 저장하는데
3. differences의 경우 첫 번쨰 루프에서 값을 저장 할 수 없으므로(2 번쨰 값부터 첫 번째 값과 뺄 수 있으므로) 이전 값이 있는 경우에만 리스트에 저장한다.
4. 가로수들 사이에 끼워넣어야 되는 가로수의 개수를 구해야 하므로 입력 받은 가로수의 위치를 정렬한다.
5. 가로수 간의 최소 간격을 구하기 위해 아까 저장한 가로수 간의 차이를 구한 리스트 differences를 돌면서 유클리드 호제법을 이용해 최대공약수를 구하고, 구한 최대 공약수 중 가장 작은 값을 저장한다.
6. 가로수 간의 차이값에서 최대 공약수를 구하는 이유는,
7. 문제가 가로수를 일정한 간격으로 최대한 적게 심기게 하기 위한 문제 이므로 두 수에서 공통되는 값들 중 가장 큰 수인 최대 공약수를 구하고,
8. 그 최대 공약수들 중 가장 작은 값이어야 모두 일정한 간격으로 심을 수 있으므로 최대 공약수 중 가장 작을 값을 구한다.
9. 이렇게 잘 구한 값으로 이제 몇 개의 가로수를 더 심어야 하는지 알아내야 하므로
10. 아까 정렬시킨 가로수 리스트를 반복 하면서 이전 가로수 와의 간격이 최대 공약수 보다 큰 녀석들이 있으면
11. 그 녀석들 사이에 가로수를 심어야 되므로,
12. 구한 간격을 최대 공약수로 나눈 값에서 -1 한 값을 더한다.
13. 이 때 -1을 하는 이유는 두 수의 간격이므로 하나는 이미 심어져 있으니 -1 을 한다.
14. 그렇게 추가로 심어야 하는 가로수의 개수를 모두 구하면
15. 끝.

---

결과

---