[Summer Winter Coding(2019) / 프로그래머스] 멀쩡한 사각형

- 문제 풀이 : https://school.programmers.co.kr/learn/courses/30/lessons/62048

 

Lv2. 문제 

풀이는 짧은데 생각을 잘해야 했던 문제다 

1. 사각형의 가로 세로가 서로소인 경우에는 대각선을 그으면 w + h - 1 만큼의 사각형을 지나간다 

이유를 생각해보니 두 수가 서로소니까 2차 평면에서 사각형 내에 정확히 지나는 점이 없다 

그래서 사각형 내부를 가르면서 지나가야하는데, 그게 각 가로에 있는 사각형 하나씩 총 w번, 

세로에 있는 사각형 하나씩 총 h번을 지나가는데 처음 사각형 하나가 겹치므로 w + h -1 을 해줘야한다. 

 

2. 만약 서로소가 아니라면 같은 크기의 사각형이 w,h의 최대 공약수(g) 갯수만큼 반복된다 

-> g * (w//g + h//g -1) 

-> w + h - g

 

이때 g == 1인 경우가 서로소인 경우이므로 일반식은 다음과 같다 

w + h - math.gcd(w,h)

전체에서 이만큼을 빼야 멀쩡한 정사각형의 갯수를 구할 수 있다

 

참고한 블로그

 

- 정답 풀이 : 

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