[Programmers] 멀쩡한 사각형 / JavaScript

문제

---

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

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

 

코드

---

function solution(w, h) {
  let answer = w * h;
  let GCD = 0;
 
  // 유클리드호제법으로 최대공약수 구하기
  const getGCD = (num1, num2) => {
    if (num2 === 0) return num1;
    else return getGCD(num2, num1 % num2);
  };
 
  GCD = getGCD(w, h);
  answer = answer - (w + h - GCD);
 
  return answer;
}

 

후기

---

• 이 문제를 풀기 위해서 최대공약수를 이용해야하고, 시간복잡도를 생각해 유클리드호제법을 사용하였다.
• 사각형의 꼭짓점을 이었을 때, 지나치는 사각형의 개수는 (사각형의 가로 + 사각형의 세로 - 가로 세로의 최대공약수) 공식으로 구할 수 있다.
• 해당 공식이 적용되는 이유는, 가로 세로가 서로소인 경우에는 항상 (가로 + 세로 - 1) 의 공식이 적용된다.
• 하지만 서로소가 아닌 경우에는 최대공약수만큼 (가로 + 세로 - 1) (이 때, 가로 세로는 서로수) 을 적용시킬 수 있다.
  

  ---

잘못된 내용이나 수정이 필요한 내용이 있으면 언제든 댓글 달아주세요 감사합니다 😀