[BaekJoon/백준] 3036번

인접한 N개의 링 사이에서

한 개의 링을 돌렸을 때, 나머지 링은 몇번 도는지에 대한 문제.

 

단계별로 문제를 풀어가는 와중인지라, 최대공약수 - 최소공배수 문제가 많이나와서

이 문제도 그런건가 했는데, 정말 그렇다..

 

 

우선 원의 지름 공식은 2πr 이다.

 

문제에서 예시로 들어놓은 12 3 8 4에 대해서 보면

24π 6π 16π 8π 이 나온다.

 

24가 첫 번째 링이니까, 이 링과 다른 링들의 최대공약수를 구해보면

그리고 문제의 출력 정답은

4/1

3/2

3/1 

 

그림과 이를 비교해보면, 느껴지는게 있다. 최대공약수로 각 수를 나눈게 기약분수형태로 취해질 수 있다는것.

#include <stdio.h>

int N; //총 링 갯수
int S; //첫 번째 링
int I; //나머지 링들을 받을 변수
int G; //GCD값

// GCD를 while문으로 구함. 재귀로도 가능.
int gcd(int a, int b) {
    
    int temp;
    
    while(b != 0) {
        temp = a;
        a = b;
        b = temp % b;
    }
    return a;
}

int main() {
    scanf("%d", &N);
    scanf("%d", &S);
    
    for(int i = 1; i < N; i++) {
        scanf("%d", &I);
        G = gcd(S, I); // 변수를 줄이기 위한 재사용
        printf("%d/%d\n",S/G, I/G);
    }
}