매일매일 알고리즘 연습(4) - 멀쩡한 사각형

작심삼일을 이겨냈다!

알고리즘 문제 링크

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

문제

멀쩡한 사각형
문제 설명
가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

제한사항
W, H : 1억 이하의 자연수
입출력 예
W	H	result
8	12	80

입출력 예 설명
입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

해결코드

function solution(w, h) {
  let gcd = getGCD(w, h);
  return w*h - ((w/gcd) + (h/gcd) - 1) * gcd;
}

function getGCD(n, m){
  return (n % m) === 0 ? m : getGCD(m, n % m);
}

추가설명

최대공약수를 베이스로 풀어야함

예시의 사진을 보면, 최대 공약수의 수만큼 반복됨을 알 수 있다
(w, h가 나눠질 수 없는 경우에는 최대 공약수는 1 이고, 패턴은 1번밖에 보여지지 않는다)

이제 결과값은 패턴의 수를 곱하면 된다는 것을 알았으니, 패턴내에서 사용할 수 있는 사각형의 개수를 알아야 한다.

패턴 내에서의 가로 길이는 pw = w / 최대공약수, 세로 길이는 ph = h / 최대 공약수 라고 볼 수 있다.

엄청 간단하지만 어려운 부분을 얘기하자면
대각선은 내려가는 동안 무조건 대각선의 가로 길이만큼의 사각형 개수를 지나간다!
동일하게 대각선은 내려가는 동안 무조건 대각선의 세로 길이만큼의 사각형 개수를 지나간다!
단, 여기서 첫 번째 출발 사각형은 가로,세로 동시에 지나간다.

이렇게 되면, 패턴 내에서 지나가는 사각형의 개수를 알 수 있다.

pw + ph -1

이제 모든 값을 알았으니 합쳐보면 풀이 끝

전체 사각형 개수 = w * h

대각선이 지나가는 사각형 개수 = pw + ph - 1

패턴 개수 = 최대공약수

사용할 수 있는 사각형 개수 = 전체 사각형 개수 - ( 패턴 개수 * 대각선이 지나가는 사각형 개수 )

잡담

진짜 코드는 간단하게 나왔는데, 개인적으로 무지막지하게 어려웠다..
pw + ph -1 공식을 떠올리는데 너무 많은 시간이 소요됐다.
처음에 내가 시도한 코드는

function solution(w, h) {
  const gcd = getGCD(w, h);
  const lean = w / h;
  const hPoint = h / gcd;
  const wPoint = w / gcd;

  let edgeCount = 0;
  for(let i=0;i<hPoint;i++){
    edgeCount += parseInt(i * lean);
  }
  
  const sum = (gcd-1) * (gcd / 2);
  const answer = edgeCount * gcd + (wPoint * hPoint * sum);

  return answer * 2;
}

최대공약수를 이용해서 패턴을 찾아내고, 패턴내에서 높이와 너비를 나눈 몫이 사용할 수 있는 사각형 개수라는 사실을 이용해서 구하는 방식이였다.
나름(?) 완벽하다는 생각에 제출햇지만, 마지막 케이스에서 타임오버가 나오면서 고생길이 시작됐다.
아무리 생각해도 타임오버가 나올 곳은 for loop 뿐이라서, 해당 for loop에서 최적화 할 수 있는 짓은 다 한 것 같다....
그렇게 모든 방법이 안통해서 멘탈은 박살났다..
그리고 아주 효과적인(?) 방법 모르겠으면 수정하지말고 다시 짜라 에 돌입했다.
코드를 다 지우고 발생의 전환으로 지나가는 부분을 구해서 빼자라는 생각으로 접근했다.
그랬더니 에이 설마... 하는 패턴이 나왔고, 그것은 곧 답이 됐다............
질질 끌리는 알고리즘은 생각의 전환을 빠르게 하는 연습도 필요할 것 같다.