알고리즘 문제
[백준] 3036번 링
feelcoding
2020. 3. 13. 03:08
728x90
https://www.acmicpc.net/problem/3036
3036번: 링
문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다. 링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면,
www.acmicpc.net
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int ring;
cin >> ring;
vector<int> v(n - 1);
for (int i = 0; i < n - 1; i++) {
cin >> v[i];
}
for (int i = 0; i < n - 1; i++) {
int gcd;
for (int j = min(v[i], ring); j >= 1; j--) {
if (v[i] % j == 0 && ring % j == 0) {
gcd = j;
break;
}
}
cout << ring / gcd << "/" << v[i] / gcd << '\n';
}
return 0;
}728x90