문제를 이해하기까지 오랜 시간이 걸렸다...
문제의 핵심은 사각형에서 직선이 지나간 사각형의 개수(= 제거된 사각형 개수)를 구하는 것이었다
따라서 w + h에서 꼭지점에서 만나게 되는 횟수(w, h의 최대공약수)를 빼주면 제거된 사각형 개수를 구할 수 있다
소스 코드
def gcd(a, b):
while b != 0:
a = a % b
a, b = b, a
return a
def solution(w,h):
wh = w*h
g = gcd(w, h)
return wh - (w + h - g)