프로그래머스 연습 문제 - 멀쩡한 사각형

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

코딩테스트 연습 - 멀쩡한 사각형

summer / winter Coding(2019)

 

from math import gcd

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

w,h가 공약수가 있을때, 공약수로 나눠 w', h'로 축소가능하다. w',h'가 서로소라 가정했을때 대각선은 반대쪽 코너에 도달하기 전 w'-1세로선과 h'-1가로선을 지나가고 지나갈때마다 새로운 정사각형이 추가된다. 그래서 첫 정사각형을 포함해 1 - (w' - 1) + (h' - 1) = w' + h' - 1개의 정사각형을 지나게 되므로 공약수를 다시 곱해주면 w + h - gcd(w,h)개의 정사각형을 지나가는 걸 알 수 있다.

 

 

최대공약수를 이용해 푼 문제. 아직도 수학문제는 감도 안잡힌다... 알고리즘 문제보다 더 어려운것처럼 느껴지는 ..ㅠㅠ 질문목록에서 설명해준걸 보고 풀었다....거의 다 알려준거나 다름없지만...