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

출처:: programmers.co.kr/learn/courses/30/lessons/62048

분류:: 최대공약수, 수학 

 

1. 문제 이해 및 해결과정

 1. 최대공약수

ex) w=8 h=12 result=80 전체 8*12 = 96 대각선 걸치는 종이 w와 h의 최대공약수 4  (8//4 + 12//4 -1) *4 = ( 2+ 3-1)*4 1. 전체에서 자를 수 있는 정사각형의 개수 w*h 2. 걸치는 것 16개 => 식 : w*h - (w+h-gcd)

 

2. 풀이방법

  1. [ python ] 내장함수 gcd이용

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

  2. [ python ] 유클리드호제법 이용

def gcd(a,b):
    a,b=8,12
    while a!=0:
        a,b=b%a,a #나머지, 나누는 수 
    print(b)
    return b        

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

 

3. 오답원인

 

4. 알게된 점