📗 멀쩡한 사각형

프로그래머스

import math

def solution(w,h):
    answer = 1
    total = w * h
    unuse = w + h - math.gcd(w, h)
    
    answer = total - unuse
    return answer

왜 이렇게 풀었을까?

• 문제에서 사용할 수 있는 정사각형의 개수를 구하기 위한 핵심은 대각선이 몇 개의 정사각형을 지나가는지 파악하는 것입니다.
• 직사각형 종이의 왼쪽 끝, 대각선이 시작하는 위치의 좌표를 (0, 0)이라고 두면 대각선이 이동하는 경로는 (0, 0)에서부터 (W, H)까지의 경로로 생각해볼 수 있습니다.
• 이때 대각선은 각 행과 열을 적어도 한 번씩은 지나가게 되며, 해당하는 정사각형의 일부를 거치게 됩니다.
• 그런데 이 중에서 대각선이 딱 격자점, 예를 들어 (2, 3)이나 (4, 6) 등을 통과할 때가 있는데, 최종적으로는 이 격자점의 개수를 빼주어야 최종 결과값이 나타나게 됩니다.
• 예시로 W가 8, H가 12라고 하면 이 둘의 최대공약수는 4이며, 이는 대각선이 총 4개의 격자점을 지나게 된다는 것을 의미합니다.
• 대각선이 격자점을 지나갈 때마다, 그 지점에서 여러 정사각형을 공유하게 되므로, 계산에서 이런 부분을 중복해서 세지 않도록 해야 합니다.