Lv2. 멀쩡한 사각형

# 문제 설명

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

# 제한 사항

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

# 입출력 예

입출력 예 설명

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

문제 해결 시 고려사항

• 멀쩡한 사각형의 개수를 구하기 위한 공식 만들기

본 문제는 주어지는 전체 사각형의 너비 w와 높이 h를 이용하여, 대각선 범위 내에 해당하는 사각형을 제외한 사각형의 개수를 구하는 문제이다.

이 문제는 w와 h를 활용한 공식을 선정하는 것이 중요하다.

w와 h의 곱으로 전체 사각형의 넓이를 구하고 너비와 높이 만큼의 사각형을 제거한 후, 너비와 높이의 최대공약수만큼 다시 더해주게 되면 대각선에 의해 제외되는 사각형을 제외한 사각형의 총 개수를 구할 수 있게 되는 것이다.

 # w와 h의 최대공약수를 구하기 위한 함수
 def gcd(w, h):
     minVal = min(w, h)
     for i in range(minVal, 0, -1):
         if w % i == 0 and h % i == 0:
             return i

 # 주어지는 사각형의 너비 w, 높이 h를 이용하여 사각형의 전체넓이를 구하고
 # 가로, 세로의 개수만큼 불가능한 사각형을 제거해준후, 앞 단계의 가로,세로에 중복되는 사각형을 계산하기 위하여
 # w와 h의 gcd 즉, 최대공약수만큼 다시 더해주면 멀쩡한 사각형의 개수를 구할 수 있다.
 return w*h-(w+h)+gcd(w,h)

필자는 위와 같이 최대공약수를 구하기 위한 gcd 함수를 별도 구현하였고, 이를 이용하여 위에서 언급한 공식대로 return 해줌으로써 문제를 해결하였다.

전체 코드

# w와 h의 최대공약수를 구하기 위한 함수
def gcd(w, h):
    minVal = min(w, h)
    for i in range(minVal, 0, -1):
        if w % i == 0 and h % i == 0:
            return i

def solution(w,h):
    # 주어지는 사각형의 너비 w, 높이 h를 이용하여 사각형의 전체넓이를 구하고
    # 가로, 세로의 개수만큼 불가능한 사각형을 제거해준후, 앞 단계의 가로,세로에 중복되는 사각형을 계산하기 위하여
    # w와 h의 gcd 즉, 최대공약수만큼 다시 더해주면 멀쩡한 사각형의 개수를 구할 수 있다.
    return w*h-(w+h)+gcd(w,h)