[백준 3036] 알고리즘 32일차 : 링

https://www.acmicpc.net/problem/3036

3036번: 링

수학3 C++

풀다가 느낀건데 수학으로 분류되는 문제는 지금의 나보다 고3의 내가 더 잘풀 것 같다.

첫번째 링을 한 바퀴 돌렸을 때 인접한 링이 도는 횟수는

첫번째 링의 둘레/인접한 링의 둘레이다. 결국 그냥 반지름의 비이다.

R1/R2 구하는거라 뭐지 왜 실버3이지 했는데 문제가 의도한건 약분이었다.

약분은 두 수의 최대 공약수로 두 수를 나눈 값을 출력하는 방법으로 구현했다.

접근 방법 요약

인접하는 원 둘레 비, 약분, 최대 공약수

 

소스코드

#include <iostream>
using namespace std;

int getGcd(int a, int b){
    for(int d = min(a,b) ; d >= 1 ; d--){
        if(a%d == 0 && b%d == 0){
            return d;
        }
    }
    return 1;
}
int main(){
    int N;
    cin >> N;
    
    int firstR;
    cin >> firstR;
    
    int radius, gcd;
    for(int i = 0 ; i < N-1 ; i++){
        cin >> radius;
        gcd = getGcd(firstR, radius);
        cout << firstR/gcd << "/" << radius/gcd << "\n";
    }
    return 0;
}