문제
상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다.
상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다.
링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 링의 개수 N이 주어진다. (3 ≤ N ≤ 100)
다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주어진다. 반지름은 1과 1000를 포함하는 사이의 자연수이다.
출력
출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다.
풀이
첫 번째 링과 나머지 링이 도는 비율은 반지름 비율과 같다. 따라서 첫 번째 링의 반지름과 각 링의 반지름의 최대공약수를 구한 뒤, 분자와 분모를 그 값으로 나눈 기약분수 형태로 출력하면 된다.
코드는 각 링마다 gcd(first, current)를 계산해서 first / gcd, current / gcd를 차례대로 출력한다. 결국 각 쌍이 독립적이어서 전체 문제도 단순한 반복 처리로 정리된다.
코드
#include <iostream>
using namespace std;
int GCD(int a, int b) {
int r = a % b;
if (r == 0) return b;
return GCD(b, r);
}
void solve() {
int n, oneRing, theotherRing;
cin >> n >> oneRing;
n--;
while (n--) {
cin >> theotherRing;
int gcd = GCD(oneRing, theotherRing);
cout << (oneRing / gcd) << "/" << (theotherRing / gcd) << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}복잡도
- 시간 복잡도: 각 링마다 최대공약수를 구하므로 이다.
- 공간 복잡도: 몇 개의 변수만 사용하므로 이다.
마무리
첫 번째 링과 나머지 링이 도는 비율은 반지름 비율과 같다.
