https://programmers.co.kr/learn/courses/30/lessons/62048?language=python3#
알고리즘 분류
- 구현
문제풀이
최대공약수를 생각해야 하는 문제다.
w,h가 서로소가 아니라면 최대공약수로 w,h를 나눠 축소시킬 수 있다.
8,12=2,3이 4개
서로소인 w,h에서 대각선은 w-1세로선, h-1가로선을 지나게 되는데 지날때마다 정사각형 1개를 지나게 된다.
그러면 첫 정사각형을 포함한 1+(w-1)+(h-1)=w+h-1개의 정사각형을 지나게 되고 최대공약수를 다시 곱해주면 해당 논리식이 나온다.
소스코드
def solution(w,h):
import math
return w*h-(w+h-math.gcd(w,h))