[백준] 3036 링 c++ - 최대공약수 이용하기 (실버4)

문제 : [3036] 링

사용 언어 : C++

등급 : 실버 4

알고리즘 분류 

• 수학
• 정수론
• 유클리드 호제법

최대공약수를 구하는 방법에 대해 잘 알고 있다면 쉽게 풀 수 있는 문제였다. 

예제 입력과 예제 출력을 살펴보면 

첫번째 입력 반지름 값 / 다른 입력 반지름 값 

인 것을 볼 수 있다. 

 

그러면 "기약 분수"를 만들어야 하는데 기약분수는 "최대 공약수"로 나눠줘야 한다. 

int GCD(int a, int b){
    if(b==0) return a;
    else return GCD(b, a%b);
}

 

해당 재귀함수를 사용해서 최대공약수를 구해주었다.

#include <iostream>

using namespace std;

int GCD(int a, int b){
    if(b==0) return a;
    else return GCD(b, a%b);
} //최대공약수 구하기 
 
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); cout.tie(nullptr);
    
int n; 
cin >> n; //반지름 개수 입력받기 
int r1, r2,gcd; //r1은 첫번째 반지름, r2는 이후에 받아지는 반지름 
cin >>r1; //r1의 값은 고정
for(int i=0; i<n-1; i++){ //'n-1'개 만큼 값을 출력해야하니깐 그만큼 반복
cin >> r2;//r2값 입력받고
gcd = GCD(r1,r2); //이는 최대공약수를 재귀함수를 이용해 나온 리턴값을 변수에 저장
cout << r1/gcd <<"/"<<r2/gcd <<"\n"; //결과값 출력 (최대공약수로 나누는 것이기 때문에 나머지 존재안해서 '/'로 나눠준다
}

return 0;
}

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

3036번: 링

배웠던 것을 이용해서 굉장히 빠르게 풀 수 있어서 기분이 좋아서 블로그를 오랜만에 쓰게 되었다 :-)

 

다른 문제들도 파이팅 !