문제링크
https://www.acmicpc.net/problem/3036
문제
상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다.
상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다.
링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 링의 개수 N이 주어진다. (3 ≤ N ≤ 100)
다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주어진다. 반지름은 1과 1000를 포함하는 사이의 자연수이다.
출력
출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다.
조건
- 시간 제한 : 1s
- 메모리 제한 : 128MB
해설
첫번째 링의 반지름을 A, 나머지 링들 중 하나의 반지름을 B라고 한다면 출력해야하는 결과값은 A/B를 약분하여 기약분수의 형태로 나타낸 꼴이다. 더이상 약분할 수 없을 때까지 약분하는 것은 A와 B의 값에 최대공약수를 나누는 것과 같으므로, 입력 값 B에 대해 A와의 최대공약수를 구해 나누어 결과를 적절히 출력해주면 된다.
최대공약수를 구하기 위해서는 a, b 값을 인자로 받아와서 두 수가 같아질 때 까지 두 수 중 큰 수에서 작은 수의 값을 빼어 큰 수를 대치해준다. 이 과정을 반복하면 최대공약수를 얻을 수 있다.
수학적인 원리는 다음과 같다.
A, B가 있을 때 A > B 이며, 이 두 수의 최대공약수가 C라고 하자.
A = a x C, B = b x C 라고 할 수 있다.
A > B 이므로,
A-B = (a-b) x C, B = b x C
A-B < B 라고 하면
A-B = (a-b) x C, B-(A-B) = (2b - a) x C
...
~~~ = 1 x C, ~~~ = 1 x C 가 되는 순간, 양쪽의 수가 같아지며, 두 수가 모두 C의 배수이므로 이렇게 구한 C가 A, B의 최대공약수이다.
풀이
최대공약수를 구하기 위한 함수를 아래와 같이 선언해주었다. a, b 값을 인자로 받아와서 두 수가 같아질 때 까지 두 수 중 큰 수에서 작은 수의 값을 빼어 큰 수를 대치한다. 이 과정을 반복하면 최대공약수를 얻을 수 있다. a, b의 값이 같을 때 반복문을 탈출하므로, 둘 중 어느 수든 반환해주면 된다.
int getGCD(int a, int b) {
while(a != b) {
if(a < b) {b = b-a;}
else {a = a-b;}
}
return a;
}
제일 첫번째 링이 회전량의 기준이 되므로, first 변수에 저장해준다. 다음 입력부터는 input 변수에 입력을 받고, first와 input의 최대공약수를 이용해 기약분수 꼴로 변환하여 출력해준다.
cin >> first;
for(int i = 1; i < N; i++) {
int input;
cin >> input;
int gcd = getGCD(first, input);
cout << first/gcd << '/' << input/gcd <<'\n';
}
코멘트
난 내가 지금까지 쓰고있던 저 GCD 구하는 알고리즘이 유클리드 호제법인줄 알았는데, 방금 검색해보니까 완전 다르네..? 성능은 모르겠지만, 이해하기 쉽고 간편한 건 내 방식인 것 같다. ㅎㅎ 저것도 분명 어떤 이름이 있겠지.
코드
#include <iostream>
using namespace std;
int getGCD(int a, int b) {
while(a != b) {
if(a < b) {b = b-a;}
else {a = a-b;}
}
return a;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N, first;
cin >> N;
cin >> first;
for(int i = 1; i < N; i++) {
int input;
cin >> input;
int gcd = getGCD(first, input);
cout << first/gcd << '/' << input/gcd <<'\n';
}
return 0;
}
Uploaded by Notion2Tistory v1.1.0