Silver IV 난이도 문제를 C++로 풀이한 내용입니다. 일정한 간격으로 나무를 심어야 하는 문제에서, 주어진 나무들의 위치를 바탕으로 추가로 심어야 할 나무의 최소 개수를 구하는 문제입니다.

백준 2485: 가로수

문제 소개

문제 번호: 2485
문제명: 가로수
난이도: Silver IV
사용 언어: C++
실행 시간: 40 ms
메모리: 3192 KB

주어진 N개의 가로수가 일정한 간격을 두고 심겨 있습니다. 하지만 일부 가로수가 뽑혀나가면서 가로수 사이의 간격이 일정하지 않게 되었습니다. 뽑혀나가기 전, 모든 가로수 사이의 간격은 동일했습니다. 이제 가로수 사이의 간격을 동일하게 만들기 위해 추가로 심어야 할 가로수의 최소 개수를 구하는 문제입니다.

접근 방법

이 문제는 주어진 가로수들의 위치를 파악하고, 이들 사이의 간격을 일관되게 만들기 위해 필요한 최소한의 나무 수를 계산하는 문제입니다.

간격 파악: 먼저, 주어진 가로수들의 위치 정보(tree)를 이용하여 각 인접한 가로수 사이의 간격(diff)을 계산합니다.
최대 공약수(GCD) 활용: 원래 모든 가로수가 일정한 간격으로 심겨 있었다는 점에 주목해야 합니다. 이는 현재 존재하는 가로수들 사이의 간격(diff 벡터의 값들)들이 모두 이 '일정한 간격'의 배수임을 의미합니다. 따라서, 모든 diff 값들의 최대 공약수(GCD)를 구하면, 원래 가로수가 심겨 있었던 '일정한 간격'을 찾을 수 있습니다.
추가 나무 계산: 구한 '일정한 간격'(GCD 값)을 기준으로, 각 diff 값에 대해 몇 개의 나무를 더 심어야 하는지 계산합니다. 예를 들어, 특정 간격이 10이고 목표 간격이 5라면, 10/5 - 1 = 1개의 나무를 더 심어야 합니다. (10m 간격에 5m 간격의 나무를 심으려면, 5m 지점에 나무를 하나 더 심어야 합니다. 10/5 = 2개의 '구간'이 되므로, 2-1=1개의 나무가 추가됩니다.)

이러한 접근 방식을 통해, 모든 diff에 대해 계산된 추가 나무 수를 합산하면 최종적인 답을 얻을 수 있습니다.

풀이 과정

입력 받기: 첫째 줄에 가로수의 개수 n을 입력받고, 이어서 n개의 가로수 위치를 tree 벡터에 저장합니다.
간격 계산: tree 벡터를 순회하며 인접한 두 나무(tree[i-1]과 tree[i]) 사이의 간격 tree[i] - tree[i-1]을 계산하여 diff 벡터에 저장합니다. diff 벡터의 크기는 n-1이 됩니다.
최대 공약수(GCD) 계산: diff 벡터에 저장된 모든 간격 값들의 최대 공약수를 계산합니다. 이를 위해 gcd_of_vector 함수를 사용합니다. 이 함수는 diff 벡터의 첫 번째 요소부터 시작하여 각 요소와 현재까지 계산된 GCD 값을 재귀적으로 계산합니다.
추가 나무 개수 계산: 계산된 최대 공약수(spacing)를 기준으로, diff 벡터의 각 간격(diff[j])에 대해 필요한 추가 나무 수를 계산합니다. (diff[j] / spacing) - 1이 각 간격에 대해 추가해야 할 나무 수이며, 이 값들을 모두 더하여 cnt 변수에 누적합니다.
결과 출력: 최종적으로 계산된 cnt 값을 출력합니다.

핵심 아이디어

원래 가로수들은 일정한 간격으로 심겨 있었다는 사실을 이용합니다.
모든 간격의 최대 공약수(GCD)가 원래의 일정한 간격이 됩니다.

주의할 점

gcd_of_vector 함수에서 첫 번째 diff[0]은 실제 간격이 아니라 더미 데이터이므로, GCD 계산 시 diff[0]을 초기 결과값으로 사용하지 않도록 주의해야 합니다 (주석에 명시되어 있음). 실제로는 diff[1]부터 시작하는 것이 더 명확할 수 있습니다. (제공된 코드는 result = diff[0]으로 시작하지만, 실제 diff[0]은 tree[1] - tree[0] 값이므로 유효한 간격입니다. 주석의 '더미 데이터 0'은 다른 맥락의 설명일 수 있습니다.)
diff 벡터의 크기는 n-1이므로, 순회 시 인덱스 범위를 올바르게 설정해야 합니다.

코드 설명

#include<bits/stdc++.h>
using namespace std;

// diff 벡터에 저장된 숫자들의 최대 공약수(GCD)를 계산하는 함수
int gcd_of_vector(const vector<int>& diff) {
    int result = diff[0]; // 첫 번째 간격을 초기 GCD 결과로 설정
    // 두 번째 간격부터 시작하여 이전 GCD 값과 현재 간격의 GCD를 계산
    // gcd(a, b, c) = gcd(gcd(a, b), c) : GCD 연산의 결합 법칙 성립
    for (size_t i = 1; i < diff.size(); i++) { 
        result = gcd(result, diff[i]); 
    }
    return result;
}

int main(){
    int n; // 가로수의 개수
    cin >> n;
    
    // tree는 각 가로수의 위치를 저장하는 벡터
    vector<int> tree(n);
    for (int i = 0; i < n; i++) {
        cin >> tree[i]; // 가로수 위치 입력
    }
    
    // diff[i] = i-1번째 나무와 i번째 나무의 간격
    vector<int> diff;
    for (int i = 1; i < n; i++) {
        diff.push_back(tree[i] - tree[i - 1]); // 인접한 나무 간격 계산 및 저장
    } 
    // diff의 크기는 n-1 : diff[0]부터 diff[n-1]까지 차있음
    
    // diff 값들의 최대 공약수 = 원래 나무 간격
    int spacing = gcd_of_vector(diff);
    
    int cnt = 0; // 추가로 심어야 할 나무의 총 개수
    // diff 벡터를 순회하며 각 간격에 필요한 추가 나무 수 계산
    for(int j = 0; j < n - 1; j++){
        // (실제 간격 / 목표 간격) - 1 : 해당 간격에 추가로 심어야 하는 나무 수
        // 예를 들어, 실제 간격 10, 목표 간격 5 => (10/5) - 1 = 2 - 1 = 1개 추가
        cnt += (diff[j] / spacing) - 1; 
    }
    cout << cnt; // 최종 결과 출력
    return 0;
}

복잡도 분석

시간 복잡도:
- 가로수 위치 입력: O(N)
- 간격 계산: O(N)
- GCD 계산: diff 벡터의 크기는 N-1이고, gcd 연산은 일반적으로 로그 시간(log(max_val))이 걸립니다. 따라서 gcd_of_vector 함수는 O(N log(max_val))에 수행됩니다.
- 추가 나무 계산: O(N)
- 전체 시간 복잡도: O(N log(max_val)) (max_val은 가로수 위치의 최댓값)
공간 복잡도:
- tree 벡터: O(N)
- diff 벡터: O(N)
- 전체 공간 복잡도: O(N)

배운 점

이 문제를 통해 저는 다음과 같은 내용을 배웠습니다.

최대 공약수(GCD)의 활용: 주어진 수들의 공통적인 배수 관계를 파악하는 데 GCD가 매우 유용하게 사용될 수 있음을 다시 한번 상기했습니다. 특히, 여러 수의 GCD는 순차적으로 gcd(a, b, c) = gcd(gcd(a, b), c)와 같이 계산될 수 있음을 확인했습니다.
문제 해석 능력: "모든 가로수 사이의 간격이 동일했다"는 조건이 문제 해결의 핵심 열쇠임을 파악하는 것이 중요했습니다. 이 조건을 통해 GCD라는 수학적 개념을 문제에 적용할 수 있었습니다.
추가 공간 계산: (간격 / 목표_간격) - 1 형태의 계산을 통해 특정 구간에 필요한 추가 요소를 계산하는 패턴을 익혔습니다. 이는 배열이나 리스트에서 '구간'의 개수를 세거나, 필요한 추가 항목을 계산할 때 유용하게 사용될 수 있습니다.

이 문제는 단순한 계산 문제처럼 보이지만, GCD라는 개념을 효과적으로 적용하는 것이 핵심입니다. 이러한 접근 방식은 나중에 더 복잡한 정렬, 분할, 혹은 패턴 관련 문제에서도 응용될 수 있을 것이라고 생각합니다.