프로그래머스 멀쩡한 사각형

1. 문제 링크

프로그래머스 멀쩡한 사각형

2. 문제 조건

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

3. 컴퓨팅 사고

• 유클리드 알고리즘 원리. 임의의 두 자연수 a, b가 주어졌을때. 둘중 큰 값이 a라고 가정해보겠습니다. n이 0일때, b가 최대 공약수(GCD)입니다. 즉, 최대공약수(GCD)를 구하는 방식을 알고있어야합니다.
  gcd(greatest common divisor)는 최대공약수의 약자인데요 최대 공약수는 어떻게 구할수 있을까요?

최대공약수 구하기
예를 들면 12,8 이라는 숫자가 있다고 가정하겠습니다. 이것의 숫자의 최대 공약수는 어떻게 될까요? 작은숫자이기 때문에 최대공약수는 4라고 하는것을 쉽게 알 수 있을것입니다.
하지만 값이 더 커질때는 암산으로 하기에는 힘든감이 있겠죠?
일단, 12와 8의 값의 최대 공약수를 구해보겠습니다. 12를 w, 8을 h라고 가정하겠습니다.
최대 공약수는 (h, w%h)의 값으로 구할 수 있습니다.

12, 8
8, 4(12를 8로 나눈 나머지)
4, 0(8을 4로 나눈나머지)

사각형의 넓이를 구하기
사각형의 넓이는 너비 * 높이로 구할 수 있습니다.

대각선방향으로 자르는 정사각형의 개수는 어떻게 구할 수 있나요?
전체 사각형 넓이 -(너비 + 높이) + 최대 공약수
의 값으로 정답을 노출해낼 수 있습니다.

W,H의 제한
W와 H의 제한은 1억이하의 자연수입니다. 따라서 long타입으로 조금 더 넓은 범위로 연산이 가능하게 하였습니다.

4. 소스 코드

class Solution {
    static int gcd(int w,int h){
        if(h == 0){
            return w;
        }
        return gcd(h, w % h);
    }
    public long solution(int w, int h) {
        int gcd_num = gcd(w,h);
        long squreArea = (long)w * (long)h;
        
        long answer = squreArea - ((long)w + (long )h) + gcd_num;
        
        return answer;
    }
}