[Programmers] 멀쩡한 사각형

[문제 핵심 : 유클리드 호제법]

• 유클리드 호제법 : 두 개의 자연수 혹은 정식의 최대공약수(Greatest Common Divisor)를 구하는 알고리즘

1. 재귀(recursive function)을 이용하는 방법

public static int gcd(int p, int q) { // p >= q이어야 한다.
  //p와 q와 대소 비교없이 들어올 경우, 여기에 조건문 처리
	if (q == 0) return p;
	return gcd(q, p%q);
 }

2. 반복문을 이용하는 방법

  public static int gcd(int p, int q) { // p >= q이어야 한다.
  //p와 q와 대소 비교없이 들어올 경우, 여기에 조건문 처리
        while(q != 0) {
            long divided = p % q;
            p = q;
            p = divided;
        }

        return p;
    }

[문제 풀이]

/*
 * @Problem     멀쩡한 사각형
 * @Url         https://programmers.co.kr/learn/courses/30/lessons/62048
 * @Author      [email protected]
 * @Created by  2021.02.19
 */

class Solution {
    public long solution(int w, int h) {
        long widthAsLong = w;
        long heightAsLong = h;

        return (widthAsLong * heightAsLong)
                - (widthAsLong + heightAsLong - gcd(widthAsLong, heightAsLong));
    }

    public long gcd(long width, long height) {
        long big = Math.max(width, height);
        long small = Math.min(width, height);

        while(small != 0) {
            long divided = big % small;
            big = small;
            small = divided;
        }

        return big;
    }
}