[Baekjoon] [2485 : 가로수]

 

가로수라는 문제이다.

 

이 문제를 읽고 생각해보면

가로수 위치와 간격에 대한 것인데, 어떻게든 간격이 작은 것에 맞춰야하고

 

간격이 2 4 6 처럼(1, 3, 7, 13)

모든 간격의 관계가 서로소가 아니면, 최대공약수의 간격으로 맞추고

그렇지 않으면 그냥 간격을 1로 하여 채워넣어야 한다는 것이다.

 

그걸 고려하면 코드가 너무나도 금방 짜인다.

 

#include<stdio.h>


int gcd(int a, int b)
{
    return b? gcd(b, a%b):a;
}


int main(void)
{
    int i, j;
    int n;
    int loc[100000] = {0,};
    int gap[100000];
    int tmp;

    scanf("%d",&n);

    for(i=0; i<n; i++)
    {
        scanf("%d",&loc[i]);
    }

    for(i=1; i<n; i++)
    {
        gap[i-1] = loc[i]-loc[i-1];
    }
    /*
    for(i=0; i<n-1; i++)
    {
        for(j=i; j<n-1; j++)
        {
            if(gap[i] > gap[j])
            {
                tmp = gap[i];
                gap[i] = gap[j];
                gap[j] = tmp;
            }
        }
    }*/
    int g = gap[0];
    int alldivg = 1;

    for(i=1; i<n-1; i++)
    {
        g = gcd(gap[i], g);
    }
    //printf("g : %d\n",g);
    for(i=0; i<n-1; i++)
    {
        if(gap[i]%g != 0)
        {
            alldivg = 0;
            break;
        }
    }

    int sum = 0;
    if(alldivg)
    {
        for(i=0; i<n-1; i++)
        {
            sum += gap[i]/g -1;
        }
    }
    else
    {
        for(i=0; i<n-1; i++)
        {
            sum += gap[i]-1;
        }
    }
    
    printf("%d",sum);

    return 0;
    
    
}

 

정렬하는 부분이 주석처리되어있는데, 입력되는 순서가 정렬되서 입력되는지 안 알려주기도 해서 그냥 정렬하는거 넣었더니

bubble 정렬이라 그런가 시간초과가 뜬다.

그리고 나머지는 그냥 생각하는대로 코드를 작성해서 그닥 효율적이진 않지만 해결 절차적으론 눈의 띌 것이다.

 

gcd를 계속 이전 결과를 인자로 하여 호출하는데 그렇게 하면 두 개의 인자만 가지는 gcd로도 여러 수의 최대공약수를 계산할 수 있다.(gcd관련 글 있으니 참고)

 

 

코드가 너무 직관적이라 할 말이 없긴 하다