문제 설명 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.
제한사항 W, H : 1억 이하의 자연수
입출력 예 W H result 8 12 80
입출력 예 설명 입출력 예 #1 가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.
import math
def solution(w,h):
gcd = math.gcd(w, h) # 최대공약수
# 한 블록 크기: w//g x h//g <- 이런 블록이 gcd만큼 존재
answer = w * h - (w + h - gcd)
return answer
처음에 이 문제를 풀었을 때 for문을 사용하여 런타임 에러가 발생했다. 딱 2문제에서 런타임 에러가 발생하더라... 애초에 수학 문제라고 생각했는데 런타임 에러를 보면서 더욱 확신했다.
for문의 로직은 일단 사각형을 좌표로 봤었고 대각선을 회귀직선이라고 생각했다. 이때 x축(w 변수)에 따른 y축 좌표를 구하고 이의 정수형까지 answer에 더하는 방식으로 접근했었다.
여기서 더 나아가 수학적 규칙을 찾아서 for문을 지웠어야 했다. 좌표로 생각했을 때 대각선이 "점(point)"을 지나는 것은 x축은 기울기의 분모 배수, y축은 기울기의 분자 배수 부분이다. 예를 들어, y = -2x + 4 라는 대각선이 있다면 (1, 2), (2, 0)가 점이 된다.
그리고 점과 점 사이에서 지워지는 사각형은 w + h - 1 개가 된다. 이는 그림을 그려보며 이해하면 쉬운데, 아래를 참고해보자.
위와 같은 사각형은 점과 점 사이의 최소 단위로 전체 w * h 크기의 사각형에선 최대공약수만큼 생성된다. 위의 y = -2x + 4 로 계속 예를 들면, 왼쪽 그림의 사각형이 2개 생성된다. 이때 2는 2와 4의 최대공약수이다.
최종적으로 지워지는 사각형은 최소 단위에서 w + h - 1 개가 되는데, 이 최소 단위 갯수는 문제에서 주어진 w와 h의 최대공약수가 되는 것이다. 이를 수식으로 표현하면 아래와 같다.
gcd: 최대공약수 gcd * (w//gcd + h//gcd - 1) = w + h - gcd
최대공약수를 math 모듈을 사용하지 않고 low level부터 구현할 수도 있겠지만, 해당 문제에서 굳이 그런 방식으로 풀 필요는 없을 것 같다.
