[C++]백준 2485번: 가로수

문제

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

2485번: 가로수

문제 이해

 

 

가로수들이 직선의 도로 한편에 심어져 있고 추가로 가로수를 심어 모든 가로수의 간격이 일정하게 되도록 하려고 한다.

이때 최소한으로 가로수를 심으려고 하는데 그 때의 가로수의 갯수를 출력해야 한다.

문제를 해결하기 위해서는 가로수 사이의 간격들을 구하고 모든 가로수 사이 간격들의 최대 공약수를 구해야 한다.

 

문제 해결

 

코드1(최대 공약수를 구하는 함수)

코드2(나무 사이의 간격들의 최대 공약수를 구하고 이를 통해 가로수 갯수 출력)

 

1. 가로수들 사이의 간격을 side 벡터에 저장함.
2. side 벡터의 원소들의 최대공약수를 구함.
3. side 벡터의 간격들을 구한 최대공약수인 maxT로 나누고 -1 한 값을 count에 저장하여 결과를 출력했습니다.