[알고리즘] 백준 2942 파이썬 - 퍼거슨과 사과

 

2942번: 퍼거슨과 사과

 

문제

맨체스터 유나이티드의 감독 퍼거슨은 빨간 사과를 R개, 초록 사과를 G개 가지고 있다. 훈련장에 있는 선수들 중 몇 명에게 나누어 주려고 한다. 단, 선수들이 서로 같은 개수의 사과를 받지 못하면 경기력 저하가 나타날 수 있으므로 모든 선수에게 같은 개수를 주려고 한다. 퍼거슨 감독은 사과를 싫어한다. 따라서 사과가 남으면 안 된다.

예를 들어, 퍼거슨이 빨간 사과를 4개, 초록 사과를 8개 가지고 있다면, 다음과 같이 세가지 방법으로 나누어 줄 수 있다.

1. 선수 1명에게 빨간 사과 4개와 초록 사과 8개를 줄 수 있다.
2. 선수 2명에게 빨간 사과 2개와 초록 사과 4개를 각각 줄 수 있다.
3. 선수 4명에게 빨간 사과 1개와 초록 사과 2개를 각각 줄 수 있다.

퍼거슨이 사과를 나누어 주는 방법을 구하는 프로그램을 작성하시오. 훈련장에 선수는 무한히 많다.

 

 

문제풀이

#01
def gcd(a,b):
    while b>0:
        a,b=b,a%b
    return a
r,g=map(int,input().split())
x=gcd(r,g)
ans=set([])
#02
for i in range(1,int(x**0.5)+1):
    if(x%i==0):
        ans.add(i)
        ans.add(x//i)
#03
for i in ans:
    print(i ,r//i ,g//i)

- #01 : 유클리드 호제법으로 최대공약수를 구하는 함수이다.

           이 함수를 통해 x에 r과g의 최대공약수를 저장한다.

- #02 : x의 제곱근까지 x의 약수를 구하여 ans에 추가해준다.

           자연스럽게 x를 i로 나눈 값도 x의 약수이니 같이 추가한다.

- #03 : 구한 ans값을 i에 하나씩 대입시켜 정답 형식에 맞게 출력한다.