[Programmers]Python_멀쩡한 사각형

문제

 

문제 설명

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

 

제한사항

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

 

코드

import math
def solution(w,h):
    n = math.gcd(w, h) #최대 공약수
    return (w * h) - (w + h - n)

 

진행 과정

 

예제 #1

W = 8

H = 12

 

개인적으로 이런 문제는 코딩 문제에 안냈으면 좋겠다... 이건 코딩 문제가 아니라 규칙을 찾는 문제라고 봐도 무방하다. 물론 이러한 문제 해결이 도움이 되긴 하겠지만 차라리 수학 공부를 따로 하겠다.

 

위 그림을 W X H = (잘린 사각형 수, 멀쩡한 사각형 수)로 확인해보겠다.

 

1 X 1 = (1, 0)

1 X 2 = (2, 0)

1 X 3 = (3, 0)

 

2 X 1 = (2, 0)

2 X 2 = (2 ,2)

2 X 3 = (4, 2)

2 X 4 = (4, 4)

 

3 X 1 = (3, 0)

3 X 2 = (4, 2)

3 X 3 = (3, 6)

3 X 4 = (6, 6)

 

정사각형일때의 경우 즉, W = H일때를 보면 한 변의 길이만큼이 잘린 사각형이 된다. 하지만 직사각형은 이러한 방법으로는 잘린 사각형 수를 찾을 수 없다.

 

직사각형일때의 경우 2 X 3, 2 X 4, 3 X 2, 3 X 4를 보면 각각 잘린 사각형 수가 4, 4, 4, 6이다. 여러 규칙을 생각한 끝에 W + H 값에 최대공약수를 뺀 값이 잘린 사각형 수가 되는 것을 알아냈다. 물론 정사각형에도 적용이 된다.

 

따라서 잘린 사각형 수는 W + H - 최대공약수가 된다. 그리고 멀쩡한 사각형 수는  W * H - 잘린 사각형 수가 될 것이다.

 

그냥 계산만하면 되는 코드이기 때문에 과정은 따로 없다.

 

예제 #1의 멀쩡한 사각형 수는 다음과같이 8 * 12 - (8 + 12 - 4) = 80이 되겠다.

programmers