프로그래머스 (멀쩡한 사각형, Summer/Winter Coding(2019)) C++

 

최소공배수를 구하는 방법으로 "유클리드 호제법"이 구글에 가장 많이 나와있어서 해당 방법을 익혀보자 다음과 같이 사용을 했다. 가로와 세로를 최대공약수로 나누어서 규칙을 찾아보려고 했지만 생각보다 규칙을 찾는게 쉽지 않아서 힘들었다. GCD 구하는 방법 하나 정도는 외우는 것도 나쁘지 않아보인다.

 

using namespace std;

long long gcd(int x, int y) {
    long long temp =0 ;
    while(y != 0) {
        temp = x % y;
        x = y;
        y = temp;
    }
    
    return x;
}

long long solution(int w,int h) {
    long long answer = 1;
    long long W = w;
    long long H = h;
    
    long long wrong = W+H - gcd(w,h);
    return (W*H)-wrong;
}