[백준] 2485번 : 가로수 - JAVA[자바]

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

2485번: 가로수

 

---

■ 문제

 

---

■ 문제 이해

가로수의 위치가 입력으로 들어온다. 예제 입력 1의 가로수 위치는 아래 그림과 같다.

심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하면 된다.

이런 식으로 같은 간격이 되도록 가로수를 심으면 된다. 따라서 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수는 3이 된다.

 

---

■ 풀이

처음 풀이할 때 헷갈렸던 부분은 같은 간격을 만들 때, 공백을 꼭 두어야 한다고 생각했다.

하지만, 공백 포함 같은 간격을 만들 수 없다면 그냥 모든 가로수를 심으면 된다. (당연한 부분이지만 생각하지 못했다.)

 

또한, 이 문제는 최대 공약수 방식으로 풀어야 하지만 홀수, 짝수를 이용한 방식으로 해결하려고 해서 시간이 오래 걸렸다.

 

나무들 사이의 거리를 구한 후 거리들의 최대 공약수를 찾는다. (2, 4, 6의 최대 공약수) 예제로 예를 들면, 2와 4의 최대 공약수를 구한 후 이 최대 공약수와 6의 최대 공약수를 찾는다.

 

2, 4, 6의 최대 공약수인 2를 구한 후, 거리마다 최대 공약수를 활용해 가로수를 심어주면 된다.

distance[i] / gcd를 해주어 나무 사이에 필요한 가로수 개수를 구한다. 이때, 이미 심어진 가로수를 빼주기 위해 -1을 해준다.

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

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

        int n = Integer.parseInt(br.readLine());

        int[] trees = new int[n];
        int[] distance = new int[n - 1];
        int treeCount = 0;
        int gcd = 0;

        for (int i = 0; i < n; i++) {
            trees[i] = Integer.parseInt(br.readLine());
        }

        for (int i = 0; i < n - 1; i++) {
            distance[i] = Math.abs(trees[i] - trees[i + 1]);

            gcd = gcd(distance[i], gcd);
        }

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

        System.out.println(treeCount);
    }

    private static int gcd(int bigNum, int smallNum) {
        if (smallNum == 0) {
            return bigNum;
        }

        if (bigNum % smallNum == 0) {
            return smallNum;
        }

        return gcd(smallNum, bigNum % smallNum);
    }
}