2942번: 퍼거슨과 사과 맨체스터 유나이티드의 감독 퍼거슨은 빨간 사과를 R개, 초록 사과를 G개 가지고 있다. 훈련장에 있는 선수들 중 몇 명에게 나누어 주려고 한다. 단, 선수들이 서로 같은 개수의 사과를 받지 못하 www.acmicpc.net 설계 빨간 사과(R)와 초록 사과(G)를 일정한 수의 선수들에게 똑같이 나눠주되, 남는 사과가 없도록 하는 경우의 수를 구하는 문제를 해결 문제의 핵심은 “모든 선수에게 같은 수의 사과를 나눠주면서 남는 사과가 없어야 한다”는 조건 → 이 조건을 만족시키기 위해 빨간 사과와 초록 사과의 수에 대한 최대공약수(Greatest Common Divisor, GCD)를 구하는 것이 중요 최대공약수(GCD)의 중요성 같은 수의 사과 배분: 빨간 사과와 초록 사과를 모..
