[BOJ 2942 // C++] 퍼거슨과 사과

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2942번 문제인 퍼거슨과 사과이다.
문제는 아래 링크를 확인하자.

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

2942번: 퍼거슨과 사과

사과를 나누어줄 사람 수는 R의 약수이면서 G의 약수들과 같음을 관찰하자.

 

따라서 R의 모든 약수를 살펴보면서 그 중 G의 약수이기도 한 값들을 골라 문제의 답을 출력할 수 있다.

 

R의 모든 약수를 찾는 것은 \(O(\sqrt{R})\)에 할 수 있고 이는 문제를 해결하기에 충분한 시간복잡도이다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int R, G;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> G;
	int i = 1;
	for (; i * i < R; i++) {
		if (R % i == 0 && G % i == 0) cout << i << ' ' << R / i << ' ' << G / i << '\n';
		if (R % (R / i) == 0 && G % (R / i) == 0) cout << R / i << ' ' << R / (R / i) << ' ' << G / (R / i) << '\n';
	}
	if (i * i == R && G % i == 0) cout << i << ' ' << R / i << ' ' << G / i << '\n';
}