Lv.2 멀쩡한 사각형

🤖문제

👍 2022년 1월 28일

<script>
  const gcd = (num1, num2) => {
      let gcd = 1;

      for (let val=2; val<=Math.min(num1, num2); val++) {
          if (num1 % val === 0 && num2 % val === 0) gcd = val;
      }
      return gcd
  }

  function solution(w, h) {
      console.log(gcd(w,h))
      return w*h - (w+h - gcd(w,h))
  }
</script>

문제에 어떻게 접근해야될지 모르겠어서 그림 열심히 그려보다가 나만의 규칙 발견해서 풀었는데 실패만 우수수수~ 도저히 모르겠어서 그냥 질문하기 보고 최대공약수를 이용하면 된다는 걸 알게되어서 그렇게 풀었다.

여기서 제일 중요한 개념은 w'와 h'가 서로소 일 때, (0,0)에서 시작하여(제일 왼쪽 위 꼭짓점) w'-1번째 라인과 h'-1번째 라인을 지나는 동안 사용할 수 없는 정사각형이 하나씩 늘어난다. 첫 번째 정사각형은 무조건 못 사용하므로 1 + (w'-1) + (h'-1) = w' + h' - 1 이다.

서로소가 아닌 경우에는 최대공약수로 나눠서 서로소로 만든 후에 위의 공식을 적용하면 이해가 된다. (예: 6X4 => 3X2)

원래의 크기에서 구할 경우에는 w' + h' - 1 에서 최대공약수만 곱해주면 되므로 <w + h - 최대공약수> 가 사용할 수 없는 정사각형의 수가 된다.