[백준문제풀이 / 정수론 및 조합론] 3036.링

문제내용

 

링들의 반지름을 입력 받고, 첫번째 링이 돌아갔을 때 나머지 링들이 몇바퀴가 도는지 구하는 문제이다.

 

풀이

나는 문제가 머리에 바로 들어오지 않을 때 예제 입력과 출력을 본다. 

그러면 가끔씩 그 문제에 대한 규칙과 해법이 나올때가 있다.

이 문제가 그랬다.

8 4 2 라는 링들의 반지름을 입력받았을 때 나오는 답인 2/1 , 4/1

즉 8/4 와 8/2 라는 것!!!

 

다른 예제 입력과 결과를 봐도 마찬가지다 !

12/3 -> 4/1        12/8 -> 3/2       12/4 -> 3/1

가설은 완료되었다. 이제 이걸 어떻게 풀어내느냐인데, 단순히 나누기로 한다면 원하는 형태의 값을 뽑아내기가 어렵다.

왜냐면 컴퓨터는 알아서 약분을 해주지 않기 때문이다.

이걸 어떻게 풀어낼까 했더니 요새 자주 풀었던 최대공약수가 머리에 스쳐지나갔다.

 

결국 

g = 첫번째링과 나머지링의 최대공약수 . 라고 한다면

(첫번째링 / g ) /  (나머지링 / g) 로 나오는 것이다.

 

#include <iostream>
#include <vector>
using namespace std;

int gcd(int a, int b)
{
	if (a % b == 0)
		return b;

	return gcd(b, a % b);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(0);	cin.tie(0);

	int n;
	cin >> n;

	vector<int> v(n);

	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}

	for (int i = 1; i < n; i++)
	{
		int g = gcd(v[0], v[i]);

		cout << v[0] / g << "/" << v[i] / g << endl;
	}

}