[ 백준 3036 ] 링 (C++)

 

3036번: 링

 

 

문제!

---

상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다.

상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다.

링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오.

 

 

---

그림을 보면 쉽게 이해할수있는 문제였습니다.

 

톱니바퀴가 서로 물려서 돌아가는 형식으로

첫번째바퀴가 한바퀴를 돌때 나머지바퀴들은 몇바퀴를 도는지를 각각 기약분수형태로 나타내는 문제입니다

 

 

몇바퀴를 도는지는 잠시 생각해보면 쉽게 알수있습니다.

첫번째 바퀴의 원둘레만큼 돌게될꺼라 생각하면 서로의 반지름 비에 의해서 결정될수 있습니다!

 

하지만 여기서 문제는 기약분수로 어떻게 나타내는가 입니다!

 

 

여기부터는 풀이

---

먼저 입력들을 받아 주었습니다.

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	vector <int>numlist;



	int N = 0;
	cin >> N;

	int memo = 0;
	int num = 0;
	cin >> memo;//최초수
	N -= 1;
	while (N--) {
		
		cin >> num;
		numlist.push_back(num);
	}

 

그리고 이 부분이 서로의 최대 공약수를 찾아 나눠주는 함수를 하나 만들어 주고

vector<int> cal(int m,int n) {//   m/n


	int p1 = m;//분모, 분자 
	int p2 = n;

	for (int i = n; i > 0; i--) {
		
		if (m % i == 0 and n%i==0) {
			p1 = m / i;
			p2 = n / i;
			break;
		}
	}

	return { p1,p2 };
}

 

 

이대로 값을 구해 각각 출력해주면 됩니다.

for (int i = 0; i < numlist.size(); i++) {
		vector <int>save = cal(memo, numlist[i]);
		cout << save[0] << "/" << save[1] << endl;

	}

 

 

최대 공약수는 유클리드 호제법으로도 구할수 있으나

유클리드 호제법 - 나무위키

 

 

이번문제는 값이 작아서 n~1까지 나눠보는 함수로 구해보았습니다.

 

ALL

#include <iostream>
#include <vector>
#include <utility>

#include <algorithm>
using namespace std;


vector<int> cal(int m,int n) {//   m/n


	int p1 = m;//분모, 분자 
	int p2 = n;

	for (int i = n; i > 0; i--) {
		
		if (m % i == 0 and n%i==0) {
			p1 = m / i;
			p2 = n / i;
			break;
		}
	}

	return { p1,p2 };
} 

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	vector <int>numlist;



	int N = 0;
	cin >> N;

	int memo = 0;
	int num = 0;
	cin >> memo;//최초수
	N -= 1;
	while (N--) {
		
		cin >> num;
		numlist.push_back(num);
	}

	for (int i = 0; i < numlist.size(); i++) {
		vector <int>save = cal(memo, numlist[i]);
		cout << save[0] << "/" << save[1] << endl;

	}

	return 0;
}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!