[프로그래머스] Lv2 - 멀쩡한 사각형 (파이썬)

코딩테스트 연습 - 멀쩡한 사각형

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을

programmers.co.kr

import math


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

풀이
1. 전체 사각형 개수(w*h)에서 (w+h-최대공약수)를 리턴

대각 선을 이은 선분이 지나는 사각형들을 위쪽과 오른쪽 끝으로 옮기면 개수가 'w+h-최대공약수'이 된다.

최대 공약수만큼 사각형이 겹치게 되므로 w+h에서 빼준다.

100% 수학문제이다. 고등학생 때 이런 로직을 다루었었던 기억이 있다.

DoIT