멀쩡한 사각형

풀이

처음에는 기울기를 이용하면 되겠다 생각하고 풀었다.
그래서 격자 1당 사용해야하는 대각선을 생각하고 추가로 풀었더니 아래처럼 풀면 되겠다라는 생각에 아래처럼 풀었다.

# 가로 세로 격자. 평행하게 격자 형태로 선이 그어져 있음
# 모든 격자칸은 1cm
import math
def solution(w,h):
    면적 = w*h
    가로 = max(w,h)
    세로 = min(w,h)
    # 격자 1당 차지 공간
    못쓰는면적 = math.ceil(가로/세로)
    총못쓰는면적 = 세로*못쓰는면적
    return 면적-총못쓰는면적

하지만 이것은 나의 착각이었다.
테스트의 반정도는 틀렸기 때문이다.

우야노 하다가 보니 최대공약수를 이용해야한다고 한다.

대각선이 지나갈때마다 격자를 사용할 수 없는데, 이것이 가로와 세로의 길이가 서로소인 경우에 못 사용하기 때문이란다.
그래서 w와h가 있으면 최대공약수g로 w/g, h/g로 만들어서 서로소로 제공하고 이를 각 더해서 중복되는 칸이 있을 것이니 -1 해준다음 이를 최대공약수 g만큼 다시 곱해주면 대각선이 지나가는 만큼을 차지한다고 한다.

음.... 더 공부해봐야되겠다. 어쨌든 그래서 또 찾고 찾아보니 아래처럼 아주 간단한 코드가 생성되었다.

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def solution(w, h):
    면적 = w * h
    최대공약수 = gcd(w, h)
    못쓰는면적 = (w // 최대공약수 + h // 최대공약수 - 1) * 최대공약수
    return 면적 - 못쓰는면적

다른 사람 풀이

왜케 똑똑이들이 많아.

def gcd(a,b): return b if (a==0) else gcd(b%a,a)    
def solution(w,h): return w*h-w-h+gcd(w,h)

from math import gcd
def solution(w,h):
    return w * h - (w/gcd(w, h) + h/gcd(w, h) - 1) * gcd(w, h)