문제 푼 날짜 : 2021-10-11

문제

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

접근 및 풀이

최대공약수를 구하고, 이를 이용하는 문제였다.
아래의 생각대로 코드를 구현하였다.

1. 가로수들 사이의 거리의 최대공약수를 구해준다.
2. 가로수들 사이의 거리를 최대공약수로 나누어준 값 -1 이 가로수 사이에 심어야하는 가로수 갯수이다.

코드

// 백준 2485번 : 가로수
#include <iostream>
#include <vector>

using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int N, before, ans = 0;
    vector<int> v;
    cin >> N;
    cin >> before;

    for (int i = 0, next; i < N - 1; i++) {
        cin >> next;
        v.push_back(next - before);
        before = next;
    }

    int diff = v[0];
    for (int i = 1; i < v.size(); i++) {
        diff = gcd(diff, v[i]);
    }
    for (int i = 0; i < v.size(); i++) {
        ans += v[i] / diff - 1;
    }
    cout << ans;
    return 0;
}

결과

피드백

최대공약수를 구하는 법도 익혀두면 유용할 것 같다.