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

문제

https://programmers.co.kr/learn/courses/30/lessons/62048?language=python3

풀이

처음에 문제를 읽고 예시그림이 너무 간결해서 눈을 의심했지만,
그렇게 간결한 예시그림을 준 이유는 무엇이겠는가?
수학적으로 접근해서 해결 하라는 것이겠지.
결국 수학적으로 접근해서 해결하면 쉽게 해결되는 문제였다.

우선 예시그림을 살펴보자 예시그림을 살펴보면, 테트리스 블럭 모양의 형태가 4회 반복되는 것을 확인할 수 있다.
여기서 힌트를 얻어야하는데, 테트리스 블럭 모양의 형태를 구성하기 위해 최소로 잡히는 직사각형을 보자.
2 * 3 = 6개가 되는 것을 알 수 있다. 이 때 2 * 3는 어떻게 이루어지는 수인가?
최소로 잡히는 직사각형의 너비와 높이는 전체 직사각형의 너비와 높이에 영향을 받는다.
그리고 예제에서는 8 * 12 직사각형에서 2 * 3 이 도출되었다.
그렇다, GCD(최대공약수)를 통해서 구할 수 있다.

직사각형 개수를 구했다면, 직사각형에서 대각선이 통과하는 블럭만 걸러내야 한다.
대각선이 통과하는 블럭의 개수는 최단거리 이동에 필요한 블럭 개수와 동일하다.
단! 최단거리 이동과 다른점은 시작점까지 더해줘야 하기 때문에 +1이 포함된다.

너비와 높이에서 각각 1을 뺀 값들을 서로 더해서 최단거리를 구하고 여기에 1을 더한다.
(2-1) + (3-1) + 1 = 4 로 대각선을 지나는 블럭의 개수가 구해진다.

여기까지 이해했다면 내용들을 모두 식으로 정리해보자.

(8 * 12) - ((2-1) + (3-1) + 1) * 4
= (w * h) - ((w/gcd - 1) + (h/gcd - 1) + 1) * gcd
= (w * h) - (w + h - gcd)

식을 코드로 작성하면 아래와 같다.

from math import gcd
def solution(w,h):
    return (w * h) - (w + h - gcd(w, h))