[멀쩡한 사각형 - python] 프로그래머스 Lv2

문제 설명

가로 길이가 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 을 반환합니다.

예시1

전략

Fig1. 직사각형1

직사각형 종이에 대각선을 그었을 때, 최대공약수만큼의 크기를 가진 직사각형을 추출합니다. 이 직사각형은 양 귀퉁이가 연결되어 있는 것을 볼 수 있습니다. Fig1의 직사각형의 가로 세로를 각각 gcd_w, gcd_h라고 가정하였을 때 흰색 직사각형의 개수는 (gcd_w + gcd_h - 1)입니다.    

Fig2 gcd_h 방향 직사각형 개수

Fig3 gcd_w 방향 직사각형 개수

Fig4 중복된 부분

Fig 2의 경우 대각선을 가로지르기 위해서는 모든 행을 가로질러야 합니다. 가로 세로의 공약수가 없는 직사각형의 경우 직선이 한칸을 이동할 때마다 꼭지점이 아닌 선분을 반드시 가로질러야 하기 때문에 Fig3의 개수가 더해집니다. 마지막으로 공통된 부분 첫번째 사각형을 없애주기 위하여 Fig4를 제거합니다. 

 

 

솔루션

import math

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

 

참조) https://leedakyeong.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%A9%80%EC%A9%A1%ED%95%9C-%EC%82%AC%EA%B0%81%ED%98%95-in-python