[Algorithm🧬] 멀쩡한 사각형

문제 / 풀이.py

버려지는 부분이 몇개인지를 찾는게 관건
솔직히.. 혼자 힘으로 찾지는 못했다.

일단 생각의 흐름대로 정리해보면,

1. 늑 모양이 반복되네? 규칙성이 있긴 하겠다.

삼각형으로 생각을 해봤는데 그건 힘들어서 사각형으로 다시 돌아와서 생각했다.

-> 8, 12 이니까 2, 3 으로 4개가 생기긴 하겠구만
-> 9, 9 면 1, 1 로 9개..?

2. 아 최대공약수!

3. 아 유클리드 호제법!!!!!!

def maxDivisor(a, b):
    if b == 0:
        return a
    return maxDivisor(b, a%b)

하고 여기까지는 코드를 짰음.. 근데 막혔다.

4. 서치해서 발견한 블로그를 참고해서 규칙성을 알아냈다.

https://taesan94.tistory.com/55

대각선이라는건 결국 시작 지점에서 끝 지점까지 가는 것! 그러려면 5칸 옆으로 3칸 위로 가야함. 근데 그걸 선으로 움직이는게 아니라 1*1 정사각형 단위로 움직이는거니까 한칸이 겹칠 수 밖에 없음. 그래서 결국 가로 + 세로 - 1 을 하면 된다.

대신 최소 단위(너비 높이 최대공약수가 1이 아닌) 사각형이 아닌데 위의 공식을 적용하면, 최대한 겹치게 할 수가 없어서 원래 답보다 더 많이 버리게 됨.

def solution(w,h):
    if w < h:
        w, h = h, w
    maxD = maxDivisor(w, h)
    trash = (h / maxD) + (w / maxD) - 1
    return w*h - maxD * trash

최종 답은 이렇게 냈다.

def solution(w,h):
    if w < h:
        w, h = h, w
    maxD = maxDivisor(w, h)
    return w*h - (w + h - maxD)

단위 사각형으로 쪼개서 생각했기 때문에 다시 최대공약수를 곱했는데, 뒤의 것을 다시 계산해서 이렇게까지 나타낼 수 있다.