LEVEL2 - 멀쩡한 사각형

https://programmers.co.kr/learn/courses/30/lessons/62048

분명 아이디어는 찾은 것 같은데.. 가장 컸던 문제는 수학에 너무나도 약한 나 자신이었다…..^^
기울기를 구하는 공식과 피타고라스 공식… 왜 아무 생각도 나지 않는것인가.. 이과였지만 문과보다 못한,, 중학생보다 못한 수학실력을 가진듯 하다(알고리즘 어떻게 풀지…핳..)
아직 제대로 이해하지는 못했지만 나중에 다시 풀때 도움이 되기 위해 작성해놓는다

일단 블로그 참고
많은 사람들이 그런것처럼 이분 블로그를 보고 이해를 하려고 노력했다

처음에는 y = 2/3x가 이해가 가지 않았다..ㅋㅋㅋㅋ

대각선은 (0,0)을 지나고 (8,12)를 지나니까 기울기는 y = (y의 증가량 / x의 증가량) * x => y = (12 - 0) / (8 - 0) * x로 계산된다
그러면 y = 3/2 * x라는 기울기 공식이 나오게 되고 직선은 x = 2, 3, 4 일때 y = 3, 9/2, 6을 지난다. 이때 점을 지나기 때문에 계산해보면 x가 2의 배수일때 y가 3의 배수일때 점을 지나게 된다 x = 2, 4, 6, 8, y = 3, 6, 9, 12

직선은 총 4개의 점의 개수를 지나게 되고 8과 12의 최대공약수라는 것을 알 수 있다

그렇다면 w와 h의 최대공약수인것을 볼 수 있는데 2개의 경우로 나눌 수 있다

1. 최대공약수가 1일때
이때는 잘려나가는 사각형의 개수가 w + h - 1이다

2. 최대공약수가 1보다 클때 - (이부분이 이해가 가질 않는다….)
이때는 8과 12처럼 일정한 블록의 수가 최대공약수만큼 반복된다. 1번의 블록의 수가 반복되는 것을 볼 수 있다
w = 8, h = 12 일때 최대공약수g는 4이다
이때 도출되는 식은 g * (w//g) + (h//g) - 1) = w + h - g
전체 사각형 개수에서 잘라지는 사각형의 개수를 빼게 되면 w * h - (w + h - g)

from math import gcd

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

코드의 결과값을 보고 굉장히 … 슬펐다…. 😧