[Programmers] (Summer/Winter Coding(2019)) Lv 2. 멀쩡한 사각형

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

프로그래머스

 

- 직사각형의 대각선이 가로지르는 사각형들은 일정한 패턴이 반복된다.

이 패턴이 반복되는 횟수가 가로 세로의  GCD

  -> GCD(12, 8) = 4

- 이 패턴의 가로 세로 길이가 각각 w / gcd, h / gcd 이다.

  -> 8 / 4 = 2, 12 / 4 = 3

- 대각선이 지나는 칸은 한줄에 1칸 ~ 2칸 존재할 수 있다.

- 대각선이므로 세로줄기준 최소 1칸은 차지할수 밖에 없다.

  -> h / gcd = 12 / 4 = 3

- 하지만 가로줄기준 2칸을 차지하는 경우는 w/gcd -1 이다.

  -> w / gcd - 1 = 8 / 4 -1 = 2 - 1 = 1

 

=> 최종식

- w * h - [ { ( w / gcd ) + ( h / gcd ) - 1 } * gcd ]

- w * h - ( w + h - gcd )

const gcd = (a, b) => b ? gcd(b, a % b) : a;

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

GitHub : https://github.com/developeSHG/Algorithm-Baekjoon_Programmers/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv2/62048.%E2%80%85%EB%A9%80%EC%A9%A1%ED%95%9C%E2%80%85%EC%82%AC%EA%B0%81%ED%98%95

GitHub - developeSHG/Algorithm-Baekjoon_Programmers: 백준 and 프로그래머스 소스코드