[프로그래머스] 멀쩡한 사각형

 

문제 설명

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.

가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

제한 사항

-W, H : 1억 이하의 자연수

입출력 예

W	H	result
8	12	80

입출력 예 설명

입출력 예 #1

가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

접근법

초반에는 좌표점에다가 사각형을 두고 대각선은 그래프로 그려서 x좌료를 w까지 늘려가며 교점을 찾았습니다. 그리고 반복문을 통해 i번째수의 y좌표를 내림, i+1번째 수의 y좌표를 올림하여 차이를 구해 못쓰는 사각형의 개수를 모두 더해주었습니다. 이렇게 하니 시간도 엄청 오래걸리고 테스트케이스6에서 오류가 났습니다!

우연히 '대각선이 지나는 격자점의 개수'라는 포스팅을 발견했습니다!

※(4)번에서 밑에서 두번째 중앙에 있는 사각형도 칠해져야 합니다!

규칙성이 보이시나요? 먼저 격자점이 있는지 없는지의 유무는 가로, 세로 길이의 최대공약수를 사용합니다! 가로, 세로 길이의 최대공약수가 2 이상이면 격자점이 생깁니다! 또한 격자점이 있는 경우와 없는 경우에서 대각선이 지나는 사각형의 개수는 다음과 같습니다.

격자점이 있는 경우 : 가로 + 세로 - 1 - 격자점의 개수 또는 가로 + 세로 - 최대공약수

격자점이 없는 경우 : 가로 + 세로 - 1

​

나의 코드

from fractions import gcd
def solution(w,h):
    if gcd(w,h) > 1: answer = w + h - gcd(w,h)
    else: answer = w+h-1
    return w*h - answer

다른 코드

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

​