<Programmers> Lv2 유클리드 호제법, GCD, LCM_멀쩡한 사각형 c++

참고- 유클리드 호제법

• (12 x 8)의 사각형에서 잘려나간 도형들은 모양을 반복하고 있는데 이 모양이 몇 번 반복되었는지 확인해본다

• 잘려나가는 도형이 외접하는 사각형 (3 X 2)의 사각형이 총 4번 반복됨을 알 수 있다
• 이는 12와 8의 최대공약수 4로 각 값을 나누면 3,2 가 된다는 사실을 알 수 있다.
• 그리고 외접하는 사각형에서 실제로 잘려나간 사각형은 w*h-1 개 이다

여기서 최대공약수를 구하기 위해 유클리드 호제법을 이용한다

📍Euclidean algorithm (참고: 위키피디아)

• 2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라고 한다 (a>b)
• a와 b의 최대 공약수는 b와 r의 최대공약수와 같다
• 이 성질에 따라 b를 r로 나눈 나머지 r'를 구하고 다시 r을 r'로 나누는 과정 반복
• 나머지가 0이 되었을 때, 나누는 수가 a와 b의 최대공약수

📍Greatest Common Divisor (GCD)

public static int gcd(int a, int b) {
	while (b>0) {
    	int tmp=b;
        b=a%b;
        a=tmp;
    }
    return a;
}

📍Least Common Multiple (LCM)

public static int lcm(int a, int b) {
	return (a*b) / gcd (a,b);
}

📝Source Code

using namespace std;

int getGCD(int a, int b) {
	while (b>0) {
    	int tmp=b;
        b=a%b;
        a=tmp;
    }
    return a;
}

long long solution(int w,int h) {
    long long answer = 1;
   
    int gcd=getGCD(w,h);
    int mw=w/gcd;
    int mh=h/gcd;
  
    long long cut=(long long)mw+mh-1;
    cut*=gcd;
   
    answer=(long long)w*h-cut;
   
    return answer;
}