1850번

1850번 - 최대공약수

한 1년전에 못 풀었던 문제를 풀어보았다.

처음에도 너무 큰 수라 당황했지만, 잘 살펴보니 쉬운 문제였다. 숫자에 집착을 버리고 문제를 봤더니 답이 보였다고나 할까?ㅋㅋㅋㅋ

아무튼 그냥 주어진 입력에 대해서 최대공약수를 구하는 문제였다, 그리고 그 만큼 1을 출력하면 끝.

쉬운 문제지만, 옛날 문제를 풀면서, 최대 공약수, 최소 공배수에 대해 다시 공부해보았다.

꼭 함수 인자를 무의식적으로 int를 써서 AC를 못받는 실수 고치기....

최대 공약수 구하는 방법 

- 2부터 두수의 미니멈까지 나누기.

- 유클리드 호제법 ( 재귀, 비재귀)

최소 공배수 구하는 방법

- 최대공약수로부터 구하기.

<정답 코드>

#include<iostream>
 
using namespace std;
 
int gcd(long long a, long long b)
{
    if (b == 0)
    {
        return a;
    }
    else
    {
        return gcd(b, a%b);
    }
}
int main()
{
    long long a, b;
    int g;
    cin >> a >> b;
 
    g = gcd(a, b);
 
    for (int i = 1; i <= g; i++)
    {
        cout << "1";
    }
    cout << endl;
 
    return 0;
}