[java] 백준 2485 가로수

 

이 문제는 최대공약수를 잘 활용해야 하는 문제이다.

 

이 문제를 잘 이해해 보면

 

 "주어진 나무들의 간격을 일정하게 했을 때 최소 몇 그루의 나무가 필요한가?" 가 핵심이다.

 

그렇다면 주어진 나무들의 간격을 최대한 넓게 유지해야 할 것이다.

 

즉 우리는 나무사이의 간격의 최대값 즉 최대공약수를 알아내야한다.

 

그렇다면 최소한 몇 그루가 필요한지 알게되고, 기존에 심긴 나무수를 제외하면 정답을 맞추게 된다.

 

우선 생각나는대로 코드를 만들었다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

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 arr[] = new int[N];
        //초기에 심겨진 나무 위치
        
        int minusArr[] = new int[N - 1];
        //나무 간격을 나타내는 배열

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        //현재 나무 위치를 저장

        for (int i = 0; i < N - 1; i++) {
            int minus = arr[i + 1] - arr[i];
            minusArr[i] = minus;
        }
        //현재 나무 사이 간격을 저장

        int max = getMax(minusArr);
        int min = getMin(minusArr);
        // 가장 넓은 간격과 가장 작은 간격의 최대공약수를 구하기 위함

        int gap = gcd(max, min);
        // 최대공약수를 저장함

        ArrayList<Integer> list = new ArrayList<>();
        // 컬렉션 사용을 위해 list를 사용

        for (int i = 0; i < N; i++) {
            list.add(arr[i]);
        }
        //list에 저장

        int maxA = getMax(arr);
        int minA = getMin(arr);
        // 반복문에 필요한 값을 얻기 위함.

        int count = 0;

        for (int i = 0; i < maxA / gap; i++) {
            if (list.contains(minA + i * gap)) {
                continue;
            } else {
                count++;

            }
        }
        System.out.println(count);

    }

    public static int gcd(int a, int b) {

        int r = a % b;

        if (r == 0) {
            return b;
        } else {
            return gcd(b, r);
        }

    }

    public static int getMax(int array[]) {
        int max = array[0];

        for (int a : array) {
            max = Math.max(a, max);

        }
        return max;

    }

    public static int getMin(int array[]) {
        int min = array[0];

        for (int a : array) {
            min = Math.min(a, min);

        }
        return min;

    }

}

 

하지만 이 코드는 문제가 많다.

 

1. 모든 나무 사이의 간격을 비교해야 하지만 최댓값과 최소값만 비교하여 오류가 발생함.

 

2. 코드가 너무나 길고 복잡하며 성능이 낮음(시간 초과)

 

따라서 그냥 푸는 방법을 생각하는 용도 정도라고 생각하면 좋겠다.

 

아래는 불필요한 부분을 모두 없엔 효율적인 방식이다.

 

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 arr[] = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        // 배열을 입력받음

        int gap = arr[1] - arr[0];
        // 나무 사이 간격 한 칸을 나타내내는 변수

        for (int i = 1; i < N - 1; i++) {
            gap = gcd(gap, arr[i + 1] - arr[i]);
        }
        // 초기값이 계산되어 있기 때문에 1부터 시작, 간격을 비교하기 때문에 N-1까지만 반복
        // i가 하나씩 증가하며 i, i + 1번째 나무 사이 간격을 모두 최소공약수 계산을한다.
        // 즉 모든 나무 사이 간격을 최소공배수로 계산한다.

        int count = 0;

        for (int i = arr[0]; i <= arr[N - 1]; i = i + gap) {
            count++;
            // 나무를 심는 최솟값을 계산.
        }

        System.out.print(count - N);
        //심은 나무의 최솟값에서 이미 심겨있는 나무를 제거
    }

    public static int gcd(int a, int b) {
        // 최대공배수 구하기

        int r;
        while (b != 0) {
            r = a % b;
            a = b;
            b = r;
        }
        return a;

    }

}

 

 

모든 나무의 간격을 비교하며, 불필요한 배열, 반복문을 모두 없애고 빠르고 효율적인 방식으로 만들었다.