[프로그래머스][JS]멀쩡한 사각형

문제

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

nm의 직사각형이 11 격자칸으로 구성되어있다.
이 직사각형의 대각선을 그었을 때 대각선이 지나가지 않는 격자칸의 개수를 구하는 문제

간단한 규칙을 찾아서 해결할 수 있었다.

해결방법

1. w(가로),h(세로)의 길이의 최대공약수를 구한다.
2. w,h를 최대공약수로 나눈 사각(가로:w/gcd(w,h) 세로:h/gcd(w,h))형
   즉, 최대공약수가 1인 사각형에서 대각선이 지나가는 블럭을 파악한다. (gcd는 두수의 최대공약수를 구하는 함수)
3. 2번에서 파악된 대각선이 지나가는 블럭 * 최대공약수를 전체의 격자칸에서 빼준다.

최대공약수가 1인 사각형의 대각선 지나는 격자칸

위 3개의 단계를 통해서 해결 할 수 있다.
여기서 문제가 생긴다. 최대공약수는 쉽게 구현할 수 있지만 최대공약수가 1인 사각형에서 빈칸은 어떻게 파악할까?

나는 3*1~~3*7 까지의 그림을 그려보면서 파악했다.

3*1 | 전체칸: 3 대각선이 지나는칸 : 3
3*2 | 전체칸: 6 대각선이 지나는칸 : 4
3*3 | 전체칸: 9 대각선이 지나는칸 : 3
3*4 | 전체칸: 12 대각선이 지나는칸 : 6
3*5 | 전체칸: 15 대각선이 지나는칸 : 7
3*6 | 전체칸: 18 대각선이 지나는칸 : 6
3*7 | 전체칸: 21 대각선이 지나는칸 : 9

위의 경우를 보면 규칙을 발견할 수있다.
x*1일때는 대각선이 x칸만큼 지워지게된다.
그 이후는 x*2,x*3,... 갈수록 대각선이 지나는칸이 x부터
1씩증가하는 것을 볼 수 있다.

어? 근데 3*3과 3*6은 1씩증가하는게 아니지 않냐 라고 물어볼 수 있다. 하지만, 저런경우는 최대공약수가 1이 아닌 경우 이기 때문에 성립되지 않는 것이다.

즉, 규칙은 최대공약수가 1인 사각형의 대각선이 지나는 격자칸의 개수 : w + h -1 이된다.

최대공약수 구현 함수 (gcd)

1. i=2부터 시작해 양쪽을 나누어준다
   1-1. 나눠진다면 result에 곱해준다.
   1-2. 나눠지지 않는다면 i++해준다.
2. i가 두 수보다 커지려고하면 종료한다.

code

function solution(w, h) {
  const multiple = gcd(w, h);
  const minW = w / multiple;
  const minH = h / multiple;
  const empty = minW+minH-1

  return w * h - multiple * empty;
}
function gcd(w, h) {
  let result = 1;
  let i = 2;
  while (w >= i && h >= i) {
    if (w % i === 0 && h % i === 0) {
      w /= i;
      h /= i;
      result *= i;
    } else {
      i++;
    }
  }
  return result;
}

업그레이드

위의 식을 조금 더 업그레이드 시킬 수있다.

function solution(w, h) {
  const multiple = gcd(w, h);
  const minW = w / multiple;
  const minH = h / multiple;
  const empty = minW+minH-1

  return w * h - multiple * empty;
}

위의 함수를 잘보자.

empty는 w와 h를 gcd(multiple)로 나누고 있고,
empty에서는 나눈 두수를 더하고 -1을 해주었다.

리턴할때는 empty를 다시 multiple에 곱해주고있다.

이걸 잘 생각해보면

function solution(w, h) {
  const multiple = gcd(w, h);
  return w * h - (w+h-multiple);
}

이렇게 축약할 수 있는것을 확인할 수 있다.
어차피 곱해준 것들을 굳이 곱해주지 않고 풀어서? 작성한 것이라고 생각하면 편하다!