[백준] 2485 : 가로수 (최대공약수, 답을 내는 방법에 대하여) - JAVA

백준 단계별 문제풀이 15단계 (약수, 배수와 소수 2)

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

2485번: 가로수

 

 

# 문제

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.

편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.

예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.

심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.

 

# 예제

입력 : 가로수의 위치를 나타내는 정수는 모두 다르고, N개의 가로수는 기준점으로부터 떨어진 거리가 가까운 순서대로 주어진다.

4
1
3
7
13

 

출력

3

 

# 필요개념

이 문제에는 두가지 조건이 있다.

1. 나무의 간격이 같아지게 나무를 추가한다.
2. 추가하는 나무의 개수는 최소

두가지 조건을 만족하는 방법은 나무 간격의 최대공약수를 사용하는 것이다.  둘의 간격을 감안하여 만들 수 있는 최대의 간격을 찾으면, 사용하는 나무의 개수를 최소화 할 수 있다.

 

 

 ✅최대공약수 ?

최대공약수를 찾는 방법은 다음과 같다.

 

즉 b가 0이 될 때까지 나누면, a가 최대공약수가 된다. (위 그림에서 연산을 한 번 더 진행해줘야 한다.)

 

여기까지 알고 있었으나, 계속 메모리초과가 떴다. 그래서 다른 풀이들을 참고해 보니, 필요없는 for문 연산이 많았다는 걸 알게 되었다. 마지막에 나무 개수를 구할 때에서 for문을 돌려 cnt 를 선언해 풀어내었는데, 그렇게 할 필요가 없었다.

첫 시작점과 마지막 시작점을 알고, 최대공약수를 알고 있으니 ((마지막 지점) - (처음 지점)) / 최대공약수 + 1 를 이용하여 개수를 구해낼 수 있었다. 여기서 추가로 심어야 하는 나무 개수를 구해야하므로, 기존에 심어져있던 개수를 빼면 된다는 것이다.

무조건 for문으로 풀어내려는 습관은 버려야한다는 것을 알게 해준 문제였다.

 

# Code

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int a = Integer.parseInt(br.readLine());
        int z = 0;
        int c = a;

        int gcd = 0;
        for (int i = 1 ; i < n ; i++) {
            int b = Integer.parseInt(br.readLine());
            int dis = b-c;
            gcd = gcd(dis, gcd);
            c = b;

            if (i == n - 1) z = b;
        }
        System.out.println((z - a) / gcd + 1 - n);
    }
    public static int gcd(int a, int b) {
        while (b != 0) {
            int rest = a % b;
            a = b;
            b = rest;
        }
        return a;
    }
}

 

# 결과