[알고리즘] 프로그래머스 2단계 - 멀쩡한 사각형

import math

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

풀이과정

1. 사진과 같은 모양이 4번 반복되어 있다. 해당 사진에서 멀쩡하지 않은 사각형의 개수는 가로(2) + 세로(3) - 1 이다.
2. 즉, "가로 + 세로 - 가로와 세로의 최대 공약수"는 멀쩡하지 않은 사각형의 개수이다.
3. 전체 사각형에서 멀쩡하지 않은 사각형의 개수를 뺀다.

새로 배운 내용

최대 공약수

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

print(gcd(8, 12))		// 12

파이썬에서 최대 공약수의 내장함수를 제공한다.

from math import gcd

print(gcd(8, 12))		// 24

최소 공배수

from math import gcd

def lcm(x, y):
    return x * y // gcd(x, y)

print(lcm(8, 12))		// 4