[C] 백준 2485번 가로수

김진웅·2023년 9월 9일

baekjoon-study

목록 보기

22/59

문제

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. 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개의 가로수는 기준점으로부터 떨어진 거리가 가까운 순서대로 주어진다.

출력

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

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

아이디어 스케치

이미 설치되어 있는 가로수의 위치가 주어지고 모든 가로수가 같은 간격이 되도록 새로 심어야하는 가로수의 최소수를 구하는 프로그램이다.
여기서 핵심은 가로수의 최소수를 구하는 것인데 이 조건이 없으면 무조건 1간격으로 가로수를 심으면 되기 때문에 이 조건을 제시한 것 같다.
같은 간격으로 가로수를 최대한 적게 심기 위해서는 현재 주어진 가로수 간격의 최대 공약수 간격으로 가로수를 심어야 한다.
현재 심어져 있는 가로수들의 간격의 최대공약수를 구한 후 최대공약수 간격으로 가로수를 심으면 된다.

코드 분할 설명

	int N;              //설치 전 가로수의 개수
    int* arr;           //설치 전 가로수
    int gcd;            //같은 간격으로 하는 최대 거리
    int cnt = 0;        //총 가로수 개수
    int* diff;          //가로수 간의 거리

    scanf("%d", &N);

    arr = (int*)calloc(N, sizeof(int));     //동적 할당
    diff = (int*)calloc(N, sizeof(int));    //동적 할당
    
    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);

필요한 변수들을 선언해준다.
문제에서는 가로수의 갯수가 3 ≤ N ≤ 100,000 이 범위로 주어져 있는데 메모리 낭비를 줄이기 위해 동적할당을 사용하였다.
동적 할당 후 기존 가로수의 위치를 입력받는다.

int GCD(int a, int b) {         //유클리드 호제법 알고리즘
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

이 문제의 핵심인 최대공약수를 구하는 알고리즘 유클리드 호제법이다.
현존하는 최대공약수를 구하는 알고리즘 중에 제일 아름답다.

for (int i = 0; i < N - 1; i++)
        diff[i] = arr[i + 1] - arr[i];

    gcd = GCD(diff[0], diff[1]);

    for (int i = 1; i < N - 1; i++)
        gcd = GCD(gcd, diff[i + 1]);

    for (int i = arr[0]; i <= arr[N - 1]; i += gcd) //최대공약수 간격으로 가로수
        cnt++;

    printf("%d", cnt - N);      //총 가로수 개수 - 기존 가로수 개수

diff배열에 인접한 가로수 간의 간격을 저장한다.
GCD함수를 이용하여 첫번째 간격과 두번째 간격의 최대 공약수를 구해 gcd에 저장한다
모든 가로수 간의 간격의 최대공약수를 구한 후 첫 가로수 부터 마지막 가로수 까지 최대공약수 간격으로 가로수를 심은 후 개수를 카운팅한다.
총 가로수 개수에서 기존 가로수 개수를 빼서 새로 심은 가로수의 개수를 구한다.

전체 코드

#include <stdio.h>
#include <stdlib.h>


int GCD(int a, int b) {         //유클리드 호제법 알고리즘
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {    
    int N;              //설치 전 가로수의 개수
    int* arr;           //설치 전 가로수
    int gcd;            //같은 간격으로 하는 최대 거리
    int cnt = 0;        //총 가로수 개수
    int* diff;          //가로수 간의 거리

    scanf("%d", &N);

    arr = (int*)calloc(N, sizeof(int));     //동적 할당
    diff = (int*)calloc(N, sizeof(int));    //동적 할당

    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);

    for (int i = 0; i < N - 1; i++)
        diff[i] = arr[i + 1] - arr[i];

    gcd = GCD(diff[0], diff[1]);

    for (int i = 1; i < N - 1; i++)
        gcd = GCD(gcd, diff[i + 1]);

    for (int i = arr[0]; i <= arr[N - 1]; i += gcd) //최대공약수 간격으로 가로수
        cnt++;

    printf("%d", cnt - N);      //총 가로수 개수 - 기존 가로수 개수

    return 0;
}