코딩 테스트 준비 1단계 기본기 - 백준 2609

코딩테스트 대비를 위해 도움이 될만한 문제 추천 블로그가 있어서 이 단계대로 코테를 준비합니다.

참조 사이트: http://covenant.tistory.com/224

코딩테스트 대비를 위한 백준 문제 추천

Part 1 준비운동 - 최대공약수와 최소공배수 (백준 2609)

문제 출처: https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

풀이

최대공약수는 유클리드 호제법으로 구하고 최소공배수는 n과 m을 곱한 값을 최대공약수로 나눈값입니다.

유클리드 호제법은 유용하고 코드가 간단하니 외워두시는 게 좋을 것 같습니다.

 

 

코드

#include<iostream>
using namespace std;
int GCD(int a, int b);
int main()
{
    int n, m;
    cin >> n >> m;
    //최대공약수->유클리드 호제법
    //최대공배수-> (n*m)/최대공약수
    int gcd = GCD(n, m);
    cout << gcd << endl;
    cout << (n * m) / gcd << endl;
    return 0;
}
int GCD(int a, int b)
{
    int c;
    while (b)
    {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}

 

결과