[백준] 2485번-가로수-Java

10 Jun 2023 in Algorithm on Algorithm

[백준] 2485번-가로수-Java

---

❓문제

1. 첫째 줄에 심어져 있는 가로수의 수를 나타내는 정수가 주어진다.
2. 둘째 줄 부터는 현재 심어져 있는 가로수의 위치가 양의 정수로 주어진다.
3. 현재 심어진 가로수를 바탕으로 모든 가로수가 같은 간격이 되려면 최소 몇개의 가로수를 심어야하는지 출력하라.

🖊️풀이법

1. 입력받은 심어져 있는 가로수들을 배열로 정의한다.
2. 각 가로수들의 거리의 차들을 계산하고, 거리의 차들의 최대 공약수를 구한다.
3. 최대공약수를 바탕으로, 총 가로수의 숫자를 구한뒤 심어진 가로수의 숫자를 뺀 뒤 출력한다.

정답 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        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 i = 0 ; i < arr.length-1; i++){
            int tmp = arr[i+1] - arr[i];
            gcd = getGCD(tmp,gcd); // 반복문을 순회하며, 가로수거리들의 최대공약수 구하기
        }
        int total = (arr[arr.length-1]-arr[0])/gcd+1; // 총 심어야 하는 가로수 
        System.out.println(total - N); // 총 심어야하는 가로수 - 심어져 있는 가로수
    }
    static int getGCD(int num1 , int num2){ //유클리드 호제법/ 최대공약수 구하기
        if(num2==0){
            return num1;
        }
        return getGCD(num2, num1%num2);
    }
}

---

정리

이번 문제는 최대공약수를 활용하여 푼다.
주의할 점은 가로수의 위치를 나타내는 정수가 1,000,000,000이며 N의 최대값은 100,000으로 너무 많은 객체를 선언하거나,
반복문을 순회하게되면 메모리 초과 또는 시간초과가 나오게 된다. 따라서, 해당 부분을 유의하여 풀자.