[백준] 3036번 : 링 - C/C++

문제부터 이해해보자.

문제에서 요구하는 것은 간단..? 하다.

 

여러 개의 링이 주어졌을 때, 첫 번째 링을 기준으로 나머지 링들이 몇 바퀴 도는지를 기약분수 형태로 나타내는 문제이다.

쉽게 말해서 첫 번째 링이 한 바퀴 돌 때, 다른 링들이 몇 바퀴 도는지를 구하는 것이다.

 

문제는 아래의 아이디어를 가지고 출발한다.

1. 기준은 첫번째 링의 반지름으로 한다.
2. 나머지 링들의 반지름을 입력받는다.
3. 첫번째 링과의 회전 비율을 고려하여 기약분수 형태로 나타낸다.
4. 최대공약수 개념을 사용한다. (기약분수 형태로 만들기 위함)

필요한 반지름 개수 n과 n개의 반지름을 입력하면 다음과 같이 코드를 작성할 수 있다.

int n;
vector<int> v;

int main(){
    cin >> n;

    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        v.push_back(x);
    }

 

왜 전역변수로 n과 vector v를 뺐냐면... 별 이유없다.

여러 문제를 풀다보니 새로운 함수를 선언하는 경우도 더러 있어서

전역으로 빼버렸다.

 

첫번째 링을 ring1이라고 하자.

int ring1 = v[0];

 

그리고 두번째 링부터 마지막 링까지 순회하면서 최대공약수를 구해서 기약분수 형태로 나타내면 된다.

for(int i = 1; i < n; i++){
   	int ring = v[i];
    int max = gcd(ring1, ring);
    cout << ring1 / max << "/" << ring / max << '\n';
}

 

gcd를 그냥 사용할 수는 없다.

필자는 C++17 버전을 사용하고 있다.

그렇다는 것은~~ 사용할 수 있다는 뜻!

C++17 이상 버전부터 

#include <numeric>

이 라이브러리를 사용하여 gcd() 함수를 제공받을 수 있다.

 

최대공약수(GCD, Greatest Common Divisor)에 대해서 알아보자.

gcd는 두 수의 공통된 약수 중에서 가장 큰 값을 의미한다.

 

gcd를 구하는 방법은 두 가지가 있다.

 

• 약수 나열법: 두 수의 약수를 각각 나열한 후 공통된 약수 중 가장 큰 값을 찾는 방법.
• 유클리드 호제법: 두 수 a,ba, ba,b에서 aaa를 bbb로 나눈 나머지를 구하고, bbb와 그 나머지로 다시 GCD를 구하는 방식으로 반복하는 방법.

 

알고리즘 문제를 해결할 때 약수 나열법 보다는 '유클리드 호제법'을 많이 사용하는 것 같다.

유클리드 호제법 공식은 아래와 같다.

𝐺𝐶𝐷(𝑎, 𝑏) = 𝐺𝐶𝐷(𝑏, 𝑎 𝑚𝑜𝑑 𝑏)

나머지가 0이 될 때 𝑏 값이 gcd이다.

 

간단하게 gcd를 구할 수 있으며, 이를 통해서 기약분수로도 쉽게 나타낼 수 있다.

 

전체 코드

#include <iostream>
#include <vector>
#include <numeric>

//링
using namespace std;

int n;
vector<int> v;

int main(){
    cin >> n;

    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        v.push_back(x);
    }
    
    int ring1 = v[0];
    for(int i = 1; i < n; i++){
        int ring = v[i];
        int max = gcd(ring1, ring);
        cout << ring1 / max << "/" << ring / max << '\n';
    }

    return 0;
}

 

 

난이도 실버4의 문제였다. 이번 문제에서의 핵심은 단연 gcd였다.

한번 익혀두면 쓰일 곳이 많은 것 같다.

이제 나는 값을 입력받을 때 배열도 잘 안 쓰고 벡터를 많이 쓴다.

벡터 사용이 익숙해지다보니, 뭔가 코딩을 잘하는 것 같기도 하고? ㅋㅋ

더 열심히 해서 pair도 익숙하게 쓰고, 문제를 해결하고 어떤 알고리즘 분류겠구나~ 라는 생각까지 했으면 좋겠다.

그러려면.. 하루에 한 문제 풀고 좋아하면 안 될 것 같긴하지만..

꾸준히 하자~~ 꾸준히!!

 

 

 

 

 

 

 

 

 

 

 

더 좋은 풀이가 있다면 댓글로 알려주세요 !!

피드백 환영입니다☺️