[Programmers] 멀쩡한 사각형

문제

https://programmers.co.kr/learn/courses/30/lessons/62048

각칸의 길이는 1x1

가로의 길이 W와
세로의 길이 H가 주어질 때,

대각선에 걸리지 않는
정사각형의 개수를 구하는
solution 함수를 완성해 주세요.

---

필요한 사전 지식

혼자힘으로 풀 수 없었다..

대각선에 걸리는 사각형의 개수를 구하는 공식

가로 + 세로 - (가로,세로의 최대공약수)

가져다 쓰기만 했지 원리는 이해하지 못했다..

유클리드 호제법

최대공약수를 구하기 위한 공식이다.

a를 b 로 나누었을 때 나머지로 b를 나누는 것을 반복해
나머지가 0이 나왔을 때 b가 a,b의 최대공약수가 된다.
ex)
12 % 15 = 12
15 % 12 = 3
12 % 3 = 0
최대공약수 = 3

재귀함수로 구현할 수 있다.

---

풀이

function solution(w, h) {

    // 유클리드 호제법으로 최대공약수 얻기
    const gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);

    // 대각선 긋기전 전체 사각형 개수
    const total = w * h;

    // 불필요한 사각형 개수 (공식: 가로 + 세로 - 가로,세로의 최대공약수)
    const unusable = w + h - gcd(w, h);

    return total - unusable;
}