[C언어] 백준 2485번: 가로수

• 문제

https://acmicpc.net/problem/2485

---

• 코드

#include <stdio.h>


// 유클리드 호제법
int gcd(int a, int b)
{
	return b ? gcd(b, a%b) : a;
}


int main(){

    int n;
    scanf("%d", &n);

    int arr[n];

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

    int gap;
    int min_gap = arr[1] - arr[0];

    // 가로수 사이 가장 작은 간격 구하기
    for(int i = 1; i < n; i++){
        gap = arr[i] - arr[i - 1];
        if(gap < min_gap){
            min_gap = gap;
        }
    }

    for(int i = 0; i < n - 1; i++){
        if((arr[i + 1] - arr[i]) % min_gap != 0){
            min_gap = gcd(min_gap, arr[i + 1] - arr[i]);
        }
    }
    
    //printf("min_gap = %d\n", min_gap);

    int count = 0; // 가로수의 수
    int check = 0;

    while(check != n - 1){
        if(arr[check] + min_gap == arr[check + 1]){
            check++;
        }
        else{
            count += (arr[check + 1] - arr[check]) / min_gap - 1;
            //printf("count = %d\n", count);
            check++;
        }
    }

    printf("%d\n", count);


    return 0;
}

---

• 문제풀이방법

1. 배열에 이미 심어진 가로수의 위치를 저장한다.
2. 1. 에서 저장한 인접한 가로수들의 위치 차이 중 최솟값을 찾아낸다.
3. 찾아낸 최솟값이 인접한 가로수들의 위치 차이의 공약수인지 확인한 후 만약 아니라면 최솟값과 가로수의 차이의 최대 공약수를 최솟값으로 업데이트한다. (최대 공약수 구하는 방법은 '유클리드 호제법' 참조)
4. 반복문을 돌면서 인접한 가로수들의 위치 차이가 최솟값이 아닐 경우 count(가로수의 수)에 가로수의 위치 차이 / 최솟값을 더한다.

3,4번 이해를 돕기 위한 설명

1

5

11

18

만약 이렇게 가로수가 배치 돼있다면 인접한 가로수들의 위치 차이의 최솟값은 1과 5의 사이인 4이다.

그러나 5와 4만큼 떨어진 곳 즉, 9 에 가로수를 심는다면 이미 심어진 11과 2 차이가 나기에 문제를 해결할 수 없다.

따라서 유클리드 호제법을 사용하여 최대 공약수를 구한 것이다.

 

유클리드 호제법 참조

유클리드 호제법 - 위키백과, 우리 모두의 백과사전