프로그래머스 / 코딩 테스트 / 멀쩡한 사각형

문제 설명

 

 

문제 해결

 

규칙을 알아내야 풀 수 있는 문제이다.

 

5 * 3 크기의 직사격형이다.

대각선이  1 * 1 크기의 정사각형 7개를 지나간다.

 

 

8 * 12 크기의 직사각형이다. 

대각선이  1 * 1 크기의 정사각형 16개를 지나간다.

 

 

5 * 4 크기의 직사각형이다.

대각선이  1 * 1 크기의 정사각형 8개를 지나간다.

 

 

2 * 8 크기의 직사각형이다.

대각선이  1 * 1 크기의 정사각형 8개를 지나간다.

 

 

직사각형의 가로의 길이를 W, 세로의 길이가 H로 정의되어 있고

대각선이 지나는 1 * 1 크기의 정사각형의 개수는 W + H한 값과 상당히 근사하게 값이 나오고 있었다.

3시간 정도 직사각형과 대각선을 그리고 패턴을 찾아본 결과 개수가 W + H - gcd(W,H)라는 결론을 얻게 되었다.

(선의 두께는 논외로 치고 최대한 얇게 만든다면 말이다.)

 

유클리드 호제법을 이용하여 최대공약수를 구할 수 있다.

하지만 math 모듈을 이용하면 함수만 호출하면 되므로 쉽게 구할 수 있다.

 

import math

def solve(w, h):
    return (w * h) - (w + h - math.gcd(w,h))

def solution(w,h):
    answer = solve(w, h)
    return answer