백준 온라인 1850번 최대공약수 C언어

오랜만에 글을 쓰는데

문제를 풀다가 기록하고 싶어서 적어본다.

 

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

1850번: 최대공약수

최대공약수를 구하는 간단한 문제이며,

모든 자리수가 1로만 이루어져 있다는게 특이점이다.

[소스코드]

#include<stdio.h>


int Euclid(long long c, long long d){

     if(d==0)
     return c;
    
     else 
        return Euclid(d,c%d);
        
 }



int main()
{
    long long a,b;
    scanf("%lld %lld",&a,&b);
    
    long long n=Euclid(a,b);
    
    for(int i=0;i<n;i++)
    printf("1");
   
    
    return 0;
}

메모리와 출력에 신경쓰면 쉬운 문제다 싶어서 풀었는데

유클리드 호제법을 사용하는 문제란걸 알았다.ㅠㅠ

 

유클리드 호제법이란 최대 공약수를 쉽게 구해주는 알고리즘 이다.

a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다는 성질에 따라서 b를 r로 나눈 나머지 값을 구하고 다시 r을 나머지 값으로 나누고, 반복해주는 그런 형식이다..

소스코드로 예를 들면 

a와 b의 값이 a=70 b=49 일때

Euclid(70,49)->Euclid(49,70%49) =>Euclid(49,21)

->Euclid(21,49%21)->Euclid(21,7)->Euclid(7,21%7)

 => Euclid(7,0)  따라서 d=0이므로 7을 리턴 해주게 된다.

즉 n은 7이고 값은 1111111 이 나오게 된다.

알아두면 간편할듯.