2485.

[1. 문제 설명]

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

---

[2. 풀이 접근]

아래와 같은 생각이 들었는데

• 간격이 제일 좁은 것 부터 1까지 줄이면서 배치하는 방식
• 간격이 짝수, 홀수가 섞여있으면 모든 간격을 1로 배치 할 수 밖에 없음 등.

여러 수들의 최대공약수를 구하면 위와 같이 복잡하게 생각할 것 없이 해결 가능하다. 

 

최대 공약수 결합 법칙

gcd(a, b, c) = gcd(gcd(a, b), c)

• GCD의 본질은 "모든 수를 나눌 수 있는 최대 정수"
• gcd(a, b) = d 라 하면, d는 a와 b를 모두 나눌 수 있고,
• 여기서 gcd(d, c) 를 구하면 결국 a, b, c 모두를 나누는 최대 정수가 된다.
• 중간에 어떤 순서로 묶든 "모두를 나누는 최대 정수"라는 본질이 변하지 않기 때문입니다.

---

[3. 코드]