백준 2485번 [가로수](C++)-yes6686- 티스토리

백준 문제 풀이: 2485 [가로수]

---

문제 링크: https://www.acmicpc.net/problem/2485

문제 설명:

직선 도로에 여러 가로수가 일정하지 않은 간격으로 심어져 있습니다. 추가로 심어야 하는 가로수의 최소 개수를 구하는 문제입니다. 새로 심는 가로수는 기존의 간격을 일정하게 나누는 위치에만 심을 수 있습니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int arr[100001];

// 유클리드 호제법을 사용하여 최대공약수 계산
int gcd(int a, int b) {
    int c;
    while (b) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int main() {
    int n;
    cin >> n;

    // 가로수 위치 입력
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 가로수 위치 정렬
    sort(arr, arr + n);

    // 모든 간격의 최대공약수 계산
    int k = gcd(arr[1] - arr[0], arr[2] - arr[1]);
    for (int i = 3; i < n; i++) {
        k = gcd(k, arr[i] - arr[i - 1]);
    }

    // 최소 추가 가로수 계산
    int ans = 0;
    for (int i = 1; i < n; i++) {
        ans += (arr[i] - arr[i - 1]) / k - 1;
    }

    cout << ans;
}

---

코드 설명

• 핵심 알고리즘: 간격의 최대공약수를 활용하여 필요한 가로수의 수를 계산합니다.
• 구현 세부사항:
  • 유클리드 호제법을 사용해 가로수 간격의 최대공약수를 구합니다.
  • 가로수 간의 간격을 최대공약수로 나눈 값에서 1을 뺀 값을 누적하여 추가로 심어야 할 가로수의 수를 계산합니다.
• 시간 복잡도: O(n log k), 여기서 k는 간격의 최대공약수를 구하는 과정에서의 값입니다.

---

결과

주어진 가로수 위치에 대해 간격을 일정하게 하기 위해 추가로 심어야 할 가로수의 최소 개수를 출력합니다. 간격의 최대공약수를 활용하여 효율적으로 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!