백준 2485번 : 가로수

---

이번 문제는 기존 가로수에 추가로 가로수를 심어 모두 같은 간격을 이루게끔 만드는 알고리즘이다. 예를 들어, 가로수가 1, 3, 7, 13의 위치에 있다면 추가로 5, 9, 11에 심어 같은 간격을 이루며 심을 수 있다.
주의해야할 것은 기존 나무들 사이에만 가로수를 추가로 설치해야한다는 점이고
기존 가로수의 위치는 랜덤이다.
다시 말해, 꼭 어떤 특정한 기준을 갖고 배치되어 있지 않다는 뜻이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws java.io.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 = arr[1] - arr[0];

        for (int i = 2; i < n; i++) {
            gcd = gcd(gcd, arr[i] - arr[i-1]);
        }

        int count = 0;
        for (int i = 1; i < n; i++) {
            count += ((arr[i] - arr[i-1])/gcd) - 1;
        }

        System.out.println(count);
    }
    public static int gcd(int x, int y) {
        if (y == 0) {
            return x;
        }
        return gcd(y, x%y);
    }
}

앞서서 주의해야할 점을 작성했는데, 그 중 두 번째 때문에 헷갈렸다.
애초에 주어진 예제가 두 개 있었는데, 모두 2씩 증가하는 짝수 혹은 홀수로 되어 있어서
완전히 헷갈려 단순히 반복문을 실행시켜 2씩 증가시키며 마지막 자연수에 도달하게끔 하고
마지막으로 기존 가로수의 개수인 n을 빼주어 전체 개수를 구했다.

이렇게 구했을 때, 당연히 예제는 맞았고
너무 쉽다는 생각을 갖고 불안해하며 답지를 제출했을 때
즉시 오답처리가 되어서 깜짝 놀랐다.

이상하다 싶어서 문제를 다시 살펴봤는데,
입력되는 자연수는 전부 랜덤이다.

어찌되었던 내가 작성한 것은 틀려서 결국 힌트를 열어보았고
힌트에 유클리드 호제법을 사용하라는 게 있었다.

이때도 사실 의아해 했는데, 최대공약수를 구해서 어떻게 풀라는 것인지 고민이 되었다.
그러다가 chatGPT에게 질문했고, 다음과 같은 순서로 연산을 하면 된다고 답을 받았다.

1. 처음 A와 B 사이의 최대공약수(거리)를 구한다.
2. 해당 결과(거리)와 C 사이의 거리에 대한 최대공약수를 구한다.
3. 1과 2를 반복하여 마지막 최대공약수를 구하면 이 것이 각 가로수 사이의 거리가 된다.

즉 결과적으로 공통되는 최대공약수를 활용하면 동일한 거리로 가로수를 심을 수 있다는 의미이다.
그래서 해당 공약수를 구하는 로직은 다음과 같다.

int gcd = arr[1] - arr[0];

for (int i = 2; i < n; i++) {
    gcd = gcd(gcd, arr[i] - arr[i-1]);
}

앞서 말한 최대공약수를 구하는 로직으로, 계속해서 A B의 최대공약수 gcd를 구하고 gcd와 C의 최대공약수를 구해나간다.
이렇게 되면 마지막 최대 공약수가 결국 가로수 사이의 거리가 되는 것이다.

그런 다음 문제에서는 가로수를 최소한 몇번 심어야되는지를 물었으므로,

int count = 0;
for (int i = 1; i < n; i++) {
    count += ((arr[i] - arr[i-1])/gcd) - 1;
}

개수를 저장할 count를 선언 후 0으로 초기화하고
해당 count 변수에 개수를 저장한다.
arr[i-1]과 arr[i] 를 최대공약수인 gcd로 나누어 주고 난 나머지가 심어야하는 가로수의 개수이다.
다만, 기존의 가로수는 제하기 위해 1을 빼준다.

---

솔직히 최대공약수를 어떻게 활용해야할지 전혀 모르겠어서
gpt에게 자세히 물어보았고, 해당 결과가 위에 작성된 내용이다.
아무래도 계속해서 예제를 뽑아보고 흐름을 질문하고 하다보니 지금은 이해를 하지만
보자마자 생각나진 않았기 때문에 생각하는 법을 길러야할 것 같다.