[백준 알고리즘] 2942번 : 퍼거슨과 사과

문제

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

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

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

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

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

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

입력

첫째 줄에 R과 G가 주어진다. (1 ≤ R, G ≤ 1,000,000,000)

출력

퍼거슨이 사과를 나누어 주는 방법을 출력한다. 방법을 출력할 때는 사과를 받게되는 선수의 수 N과 나누어 주는 빨간 사과의 수 X와 초록 사과의 수 Y를 출력한다.

각 방법은 한 번만 출력해야 한다. 나누어 주는 방법은 아무 순서로 출력해도 된다.

예제 입력 1

4 8

예제 출력 1

1 4 8 2 2 4 4 1 2

 

내가 작성한 코드 (C++ 성공)

#include <iostream>

using namespace std;

int gcd(int a, int b){
	int n;

	while(b!=0){
		n=a%b;
		a=b;
		b=n;
	}
	
	return a;
}

int main(){
	int r, g, n;
	
	cin >> r >> g;
	
	n = gcd(r, g);
	
	for(int i=1; i<=n; i++){
		if(n%i == 0){
			cout << i << " " << r/i << " " << g/i << "\n";
		}
	}
	
	return 0;
}

 

정리

이 문제는 최대공약수를 이용한 문제였다.
그래서 유클리드 호제법이라고 불리는 알고리즘을 이용해서 문제를 풀었다.
그리고 반복문을 통해 최대공약수를 나눈 나머지가 0이 되면 출력해주었다.