[C++]백준 - 3036번 문제

3036번: 링 (acmicpc.net)

3036번: 링

 

3036번 : 링

---

상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다.

상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다.

링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 링의 개수 N이 주어진다. (3 ≤ N ≤ 100)

다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주어진다. 반지름은 1과 1000를 포함하는 사이의 자연수이다.

 

 

출력

---

출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다.

 

 

 

---

 

생각해 볼 점

---

링의 둘레의 길이의 비를 구하는 문제라고 봐도 무방합니다.

둘레의 길이는 (4pi * r)이지만, 비례 문제에서는 4pi를 굳이 곱할 필요가 없습니다.

 

첫번 째 링의 반지름을 구하고, 두번 째 링부터는 첫번 째 링을 한 번 회전 시켰을 때, 몇번 돌아갈 지 생각합니다.

 

예시)

 

첫번 째 링의 r = 12

두번 째 링의 r = 8

 

12 / 8 = 1.5바퀴가 돌아갈 것입니다.

출력 형식은 기약분수 형태여야 하므로, 3/2이 정답입니다.

 

기약 분수를 만드는 방법은 분자, 분모가 서로소여야 하므로 최대 공약수로 나누어주면 됩니다.

 

예시에서는 최대 공약수(g) = 4 이므로

12 % g / 8 % g = 3/2 형태로 출력할 수 있습니다.

 

코드

---

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
    if(a < b)
    {
        int temp = b;
        b = a;
        a = temp;
    }
    while(b > 0)		//유클리드 호제법
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main()
{
    int N;
    cin >> N;
    int ring[100];
    for(int i = 0; i < N; i++)
    {
        cin >> ring[i];
    }
    
    for(int i = 1; i < N; i++)		//2번 째 요소부터 기약분수 형태로 출력
    {
        int g = gcd(ring[0], ring[i]);
        cout << ring[0] / g << "/" << ring[i] / g << "\n";
    }
    
    return 0;
}

 

그 외

---