Solved problems
BOJ 2485 - 가로수
coloredrabbit
2018. 1. 17. 15:51
재밌는 문제라 포스팅하고자 한다.
연속된 숫자 1,5,10 이라고 한다면 심어야할 나무는 1보다 작은 위치 또는 10을 넘어가는 위치에 심을 순 없다. 따라서 1-5 간격과 5-10 간격이 다르기 때문에 각 구간에 나무를 심어야되는데, 그 간격을 정해보는 것에 포커싱을 맞춰보자. 1-5 간격은 4, 5-10 간격은 5다. 따라서 2도 3도 4,5 모두 간격으로 둘 수 없다. 따라서 1간격으로 나무를 심을 수 밖에 없다.
반면 1,5,11 이라고 가정해보자. 1-5 간격은 4, 5-11 간격은 6이 된다. 따라서 2간격만큼 나무를 심어줄 수 있다.
모든 구간에 대해 같은 간격으로 나눠져야하기 때문에 최대공약수를 이용해 구한다.
모든 간격에 대해 최대공약수를 구하면 그것을 나눈 값 - 1로 답을 구할 수 있다.
#include <cstdio> #include <algorithm> using namespace std; int gcd(int a, int b) { int t; while (b) { t = a%b; a = b; b = t; } return a; } int main() { int N, *A,g,i,ans=0; scanf("%d", &N); A = new int[N]; for(i=0;i<N;i++) scanf("%d", &A[i]); sort(A, A + N); g = gcd(A[1] - A[0], A[2] - A[1]); for (i = 2; i < N - 1; i++) g = gcd(g, A[i + 1] - A[i]); for (i = 0; i < N - 1; i++) ans += (A[i + 1] - A[i]) / g - 1; printf("%d", ans); return 0; }