[백준알고리즘] 3036번: 링 -C

[백준알고리즘] 3036번: 링 -C

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

3036번: 링

 

이 문제는 간단했습니다.

 

출력은 (첫번째 링의 반지름 / i번째 링의 반지름)을 약분해서 구하면 됩니다.

 

 

이유는 첫 번째 링의 한 바퀴를 도는 거리는 첫 번째 링의 둘레와 같기 때문에 2*Pi*r1입니다.

첫 번째 링의 한 바퀴 돌 때 두 번째 링도 같은 거리만큼 돌아야 하기 때문에 2*Pi*r1 = 2*Pi*r2 * x가 되어야 합니다. (x는 두번째 링이 도는 횟수)

따라서 r1 = r2 * x이며, x = r1 / r2가 되기 때문입니다.

 

 

다시 돌아가서 (첫 번째 링의 반지름 / i번째 링의 반지름)을 약분해서 출력해야 하기 때문에 두 수의 gcd를 구한 후 각각 나눠준 후 출력하도록 하면 됩니다.

 

 

#include <stdio.h>

int get_gcd(int a, int b){
    int ta = a > b ? a : b;
    int tb = a > b ? b : a;
    int t;

    do{
        t = (int)(ta % tb);
        ta = tb;
        tb = t;
    }while(tb != 0);

    return ta;
}

int main(void){
    int N, i, gcd;
    int ring[100];

    scanf("%d", &N);
    for(i = 0; i < N; i++){
        scanf("%d", &ring[i]);
    }

    for(i = 1; i < N; i++){

        gcd = get_gcd(ring[0], ring[i]);
        printf("%d/%d\n", ring[0]/gcd, ring[i]/gcd);
    }

    return 0;
}

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다