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

백준 2485번: 가로수 링크

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

문제를 풀기 전 생각한 것

가로수 사이의 거리 = 다음 가로수 - 가로수
가로수 사이 거리의 최대공약수를 처음 위치에 더함

풀면서 어려웠던 점

최대공약수를 구하는 함수를 따로 만들기 싫었지만 어쩔 수 없이 만들었다.

코드

#include <stdio.h>
int tree[100000];
int distance[100000];

int make_gcd(int a, int b)
{
    if (b == 0)
    {
        return a;
    }
    else
    {
        return make_gcd(b, a % b);
    }
}

int main(void)
{
    int N;
    int cnt = 0;
    int gcd = 0;

    scanf("%d", &N);

    for (int i = 1; i <= N; i++) {
        scanf("%d", &tree[i]);
    }

    for (int i = 1; i < N; i++) {
        distance[i] = tree[i + 1] - tree[i];
    }

    for (int i = 1; i < N; i++) {
        gcd = make_gcd(gcd, distance[i]);
    }

    for (int i = 1; i < N; i++) {
        cnt += (distance[i] / gcd) - 1;
    }

    printf("%d", cnt);

    return 0;
}

풀면서 배운 점

X