[프로그래머스] 멀쩡한 사각형 - python 풀이

본 게시물은 프로그래머스의 연습 문제 풀이입니다. 저작권은 (주) 그랩에게 있습니다

파이썬 코드

# 멀쩡한 사각형

# 입력받은 두 수의 최대 공약수를 구하는 함수
def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)


def solution(w, h):
    # w와 h의 최대공약수 구하기
    w_h_gcd = gcd(w, h)
    # 총 정사각형의 수
    total_square = w * h
    unusable_square = w + h - w_h_gcd
    # 사용할 수 있는 정사각형의 수
    usuable_square = total_square - unusable_square
    return usuable_square

Comment

답을 구하기 위해서는, 전체 정사각형의 개수에서 사용할 수 없는 정사각형의 개수를 빼야한다.

전체 정사각형의 개수 는 주어진 w와 h를 곱하면 쉽게 구할 수 있다.

사용할 수 없는 정사각형의 개수는 w와 h의 최대공약수에 따른 규칙을 찾아서 구해내야한다. 최대공약수를 구하기 위해서 유클리드 호제법을 재귀함수의 형태로 구현한다. 최대공약수에 따른 사용할 수 없는 정사각형의 개수 규칙은 아래와 같다

 

w + h - g

 

위와 같은 규칙이 나오는 이유는, 대각선은 좌측 상단의 꼭지점으로부터 우측 하단의 꼭지점으로 우하향한다. 이때, 대각선은 가로로 w만큼 세로로 h만큼 지니간다. 그러므로 당연히 w개의 정사각형을 못쓰게 될 것이고 h개의 정사각형을 못쓰게 된다. 그러므로 w와 h를 더한다. 하지만, 대각선으로 지나가는 것이므로 실제 값보다 과대 계산된다. 겹치게 계산된 수 (w와 h의 최대공약수)를 빼준다.

Reference

프로그래머스