intro : 가로수길 걷다가 이 문제가 생각날것만 같다.

문제

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다. 편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다. 예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다. 심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.

입력

첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 1,000,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르고, N개의 가로수는 기준점으로부터 떨어진 거리가 가까운 순서대로 주어진다.

출력

모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.

문제 풀이 (220ms)

import java.io.*;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입출력을 위한 BufferedReader, BufferedWriter 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 반복 횟수 변수 선언
        int forCount = Integer.parseInt(br.readLine());
        // 입력값 배열 선언 
        int[] array = new int[forCount];
        for (int i = 0; i < array.length; i++) {
            array[i] = Integer.parseInt(br.readLine());
        }
        // 오름차순으로 정렬 (각 가로수의 순차적인 차이를 알기 위해서 정렬)
        Arrays.sort(array);
        // 가로수의 각 차이를 저장할 배열 선언
        int[] gap = new int[array.length - 1];
        // 반복문을 통해 i + 1 인덱스의 가로수와, i 인덱스의 가로수의 거리 차이를 계산
        for (int i = 0; i < array.length - 1; i++) {
            gap[i] = array[i + 1] - array[i];
        }

        
        int gapStand = gap[0];
        for (int i = 1; i < gap.length; i++) {
            // 반복문을 통해 최대공약수를 계산
            gapStand = gcm(gap[i], gapStand);
        }
        
        int result = 0;
        for (int g : gap) {
            // 각 가로수간의 차이를 최대공약수로 나눈 몫에 - 1 값이 새로 심어야 하는 가로수의 개수
            result += (g / gapStand) - 1;
        }

        // bw로 출력하기 위해 문자열로 변환 후 write
        bw.write(String.valueOf(result));
        bw.flush();

        // 자원 반납
        bw.close();
        br.close();
    }

    // 최대공약수를 구하는 메소드
    // 유클리드 호제법 
    // return 해야하는 값(최대 공약수)는 몫이다.
    public static int gcd(int a, int b) {
        while (b > 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}

문제 해석

생각보다 까다로웠다고 느낀 문제였다. (뭔가 풀이방법이 직관적으로 보이지않는 문제들은 난이도 레벨 이런거랑 상관없이 항상 까다롭다고 느낀다.) 각 가로수 간의 차이를 최대공약수를 통해 가로수의 간격이 같을 수 있도록 할 수 있는데. 이또한 문제를 그림으로 그려보다가 알게되었다.

만약 주어진 값이 아래와 같다면 같은 간격을 유지한채로 가로수를 심으려면 결국 2만큼의 간격마다 가로수를 심어야 한다는 것을 알 수 있다. 3칸 간격으로 가로수를 심자니 1과 3 사이의 간격이 2이므로 3칸 간격으로 심을수 없고 1칸 간격으로도 심을 수 있으나, 문제의 조건이 새로 심어야 하는 최소수를 구하는 것이기에 2칸 간격으로 가로수를 심어야 한다.

입력값 : 1  3  7  13

1과 3의 차이 : 2 
3과 7의 차이 : 4 
7과 13의 차이 : 6

2 4 6의 최대 공약수는 ? [2]

그러면 2칸 간격마다 가로수를 새로 심게되는데 이때 다음과 같이 새로운 가로수를 심게 된다.

1 3 [5] 7 [9] [11] 13
[5],[9],[11] 3개의 가로수를 새로 심어야 한다.

근데 우리가 계산해야하는 결과는 새로심는 가로수의 개수이기에 다음과 같은 계산방법을 통해 추출 할 수 있다. (가로수 사이의 차이 값 / 최대공약수) - 1 예시를 들어보자면, 7과 3의 차이는 4이다. 4 / 최대공약수(2) - 1은 1이다. 3과 7 사이에 새로 심는 가로수의 개수는 1개이다, 13과 7의 차이는 6이다. 6 / 최대공약수(2) - 1은 2이다. 7과 13 사이에 새로 심는 가로수의 개수는 2개이다.

이렇게 최대공약수를 통해 간격을 통일하고 추가 가로수의 최소 개수를 구하는 방식으로 문제를 해결할 수 있다. 문제를 처음에는 어렵게 느꼈지만, 최대공약수 활용이라는 공식을 통해 간결하게 풀이할 수 있다는게 신기한거 같다.

I am visible

contact

문제

입력

출력

문제 풀이 (220ms)

문제 해석