🕊 Link

Lv2. 멀쩡한 사각형 Javascript
https://programmers.co.kr/learn/courses/30/lessons/62048

🧑🏻‍💻 Code(javascript)

function solution(w, h) {
  const nums = [w, h];
  let a = Math.min.apply(null, nums);
  let b = Math.max.apply(null, nums);
  let gcd = 0;
  for (let i = 1; i <= a; i++) {
    if (a % i === 0 && b % i === 0) gcd = i;
  }

  return a * b - (a + b - gcd);
}

💡 Solution

참고: 유튜브 DogezaPro_2.0

1. 직선 방정식을 통해서 기울기는 $-w/h$
   $-(w/h) = -(b * gcd / a * gcd)$
   $(*gcd는 최소공배수)$
   즉, 전체 도형을 자르는 대각선과 작은 정사각형의 꼭지점과 만나는 곳은 gcd개가 존재함.

2. 위 조건에 따라서 만나는 꼭지점과 꼭지점 사이의 직사각형이 gcd개 존재하고
   직사각형 속의 잘리는 정사각형의 갯수를 구한 후 gcd를 곱해주면 된다.

3. 최단거리를 구하는 방법에 따라서 꼭지점과 꼭지점 사이의 직사각형 내에서 잘리는 정사각형 갯수는
   $a+b-1$

4. 마지막으로 직선이 지나가지 않는 직사각형의 갯수는
   $w * h - gcd(a+b-1)$
   = $w * h - (w+h-gcd)$

function solution(w, h) {
  // 작은 값을 a에, 큰 값을 b에 할당함.
  const nums = [w, h];
  let a = Math.min.apply(null, nums);
  let b = Math.max.apply(null, nums);
  let gcd = 0;
  // 최대공약수를 구하는 공식
  for (let i = 1; i <= a; i++) {
    if (a % i === 0 && b % i === 0) gcd = i;
  }
  return a * b - (a + b - gcd);
}

👨🏻‍💻💭 Self Feedback

다방면으로 패턴을 찾아보려고 했으나 최대공약수나 최단거리 등의 방법은 생각하기 어려웠다.
디바이드 앤 컨커 (divide and conquer) 분할 정복. 쪼개고 쪼개 보는 연습 필요.

// 최대공약수 재귀함수
function solution(w,h){
    const gcd = (a, b) => {
        return b === 0 ? a : gcd(b, a % b);
    };
    return w * h - (w + h - gcd(w, h));
}

• 2021.04.19 - 최초 작성

• 참고
  유튜브 DogezaPro_2.0 https://www.youtube.com/watch?v=LZ94TH5L--8

댓글 환영 질문 환영
by.protect-me