백준 2485번 : 가로수 (C 언어)

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

2485번: 가로수

Code:

#include <stdio.h>
#include <limits.h>
 
int gcd(int a, int b)
{
    if (b == 0)
    {
        return a;
    }
    else
    {
        return gcd(b, a % b);
    }
}
 
int main()
{
    int arr[100000] = { 0 };
    int n;
    scanf("%d", &n);
    int i = 0;
    int num[100000] = { 0 };
    int count = 0;
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &arr[i]);
    }
    for (int i = 1; i < n; i++)
    {
        num[i] = arr[i+1] - arr[i];
    }
    int gcd_min = arr[2] - arr[1];
    for (int i = 1; i < n; i++)
    {
        gcd_min = gcd(gcd_min, num[i]);
    }
    for (int i = 1; i < n; i++)
    {
        count += (num[i] / gcd_min) - 1;
    }
    printf("%d\n", count);
    return 0;
}

문제 설명:

이 문제는 직선 도로 한 편에 이미 심어져 있는 가로수의 위치와 간격을 고려하여, 추가로 가로수를 최소한으로 심어야 하는 경우를 찾는 문제입니다. 가로수들은 동일한 간격으로 심어져야 하며, 이미 심어져 있는 가로수의 위치와 간격이 주어집니다. 새로 심어야 하는 가로수의 최소 개수를 찾는 것이 목표입니다.

코드 설명:

이 C 프로그램은 주어진 가로수의 위치와 간격을 기반으로 모든 가로수 간의 간격을 동일하게 만들기 위해 추가로 심어야 하는 가로수의 최소 수를 계산합니다.

1. gcd 함수는 두 정수의 최대공약수를 재귀적으로 계산합니다.
2. arr 배열에는 이미 심어져 있는 가로수의 위치를 저장하고, num 배열에는 가로수 간의 간격을 저장합니다.
3. 루프를 사용하여 각 가로수 간의 간격을 계산합니다.
4. 모든 간격의 최대공약수를 찾기 위해 gcd 함수를 사용합니다.
5. 추가로 심어야 하는 가로수의 수를 계산하고 count 변수에 더합니다.
6. 마지막으로 결과를 출력합니다.