C++) 백준 2485번: 가로수 (최대공약수 문제)

https://www.acmicpc.net/problem/2485

2485번: 가로수

글을 쓸까말까 하다가 다시 헛짓거리하지 않기 위해 되새김질 하는 의미에서 쓰려한다.

일단 문제는 최대공약수를 이용하는 문제이다. 그림을 그려보거나 조금만 생각해봐도 이건 생각해낼 수 있는데, 내가 문제가 되었던 점은 '지금까지 푼 최대공약수 문제들은 입력값이 두 개밖에 없었는데 이건 너무 많은데 어떡하지?'였다. 그래서 선택한 방법이 브루트 포스 방법으로 모든 최대공약수들을 찾아내어 그 중 최댓값을 쓰는 것이었는데.. 입력의 최대값이 1000000000인 걸 인지하고 방향을 돌렸어야했다.. 아니나다를까 알고리즘에는 문제가 없었지만 시간초과. 애초에 그렇게 풀지말라고 문제를 이렇게 낸 게 아닐까 싶다.

따라서 다른 방법을 생각해내야 했는데, 이는 내가 최대공약수의 성질을 제대로 생각해보지 않아서 발생한 문제였다. 조금만 생각해보면 최대공약수를 구하는 함수를 만들어놨으니 그냥 반복문으로 하나하나 다 돌리면 결국 마지막에 남는 건 모든 수의 최대공약수 뿐인 것이다.

 

아래는 코드이다.

 

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int gcd(int a, int b);

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

int N;
cin >> N;

int* arr = new int[N];
for (int i = 0; i < N; i++) {
cin >> arr[i];
}

sort(arr, arr + N);

int gcd_num = 0, min = 1000000001;
for (int i = 0; i < N - 2; i++) {
gcd_num = gcd(arr[i + 2] - arr[i + 1], arr[i + 1] - arr[i]);
if (min > gcd_num)
min = gcd_num;
}

cout << (arr[N - 1] - arr[0]) / min - 1 - (N - 2);

delete[] arr;

return 0;
}

int gcd(int a, int b)
{
int r = a % b;
if (r == 0)
return b;
else
return gcd(b, r);
}