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

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

코딩테스트 연습 - 멀쩡한 사각형

나의 풀이

function isCoprime(a, b) {
    return a % b ? isCoprime(b, a % b) : b;
}

function solution(w, h) {
    return isCoprime(w, h) === 1 ? (w * h) - (w + h - 1) : (w * h) - (w + h - isCoprime(w, h));
}

직각 사각형의 크기에 따라 교착점을 지나는 것이 있고, 지나지 않는 것이 있다.

 

가로와 세로의 길이가 서로소인 경우, 교착점이 없으며 이때 대각선이 지나는 사각형의 개수는 가로 + 세로 - 1이다.

서로소가 아니라면 가로 + 세로 - 1 - (가로, 세로의 최대공약수 - 1)이다.

 

이에 따라 최대 공약수를 유클리드 호제법으로 구하고, 최대 공약수를 바탕으로 서로소를 판별하였다.

삼항 연산자로 서로소인 경우, 아닌 경우에 따라 사각형의 개수를 계산하였다.

 

간단하지만 재귀 함수를 사용해보았다!! 너무 뿌듯하다 ㅎㅎ