문제
접근
규칙을 찾는데 생각보다 오랜 시간이 걸렸다.
우선 w, h의 최대공약수만큼 패턴이 반복된다는 것은 쉽게 찾을 수 있었다.
예제에서의 경우 8, 12의 최대공약수인 4회 패턴이 반복된다.
결국 전체 수식은 다음과 같을 것이다.
전체 사각형의 수 - (패턴에서 잘리는 사각형 * 최대공약수)
문제는 패턴안에서 잘리는 사각형의 개수를 어떻게 찾을지이다.
나는 1x1부터 4x3까지 직접 그려봤다..
그리고 잘리는 사각형의 개수가 w+h-1이란 것을 발견했다.
정확히는 모르겠지만 원점 부터 대각선 끝점까지 선을 그리면 가로의 개수와 세로의 개수만큼이 포함되고, 이게 겹 치는 점이 하나 생기게 된다.
최종적인 식은 다음과 같다.
w x h - (w/GCD + h/GCD -1) x GCD = (w x h) - (w + h - 1)
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(w,h):
if w < h:
w, h = h, w
n = gcd(w,h)
answer = w*h - (w+h-n)
return answer
def gcd(a,b):
while b != 0:
n = a % b
if n==0:
return b
a = b
b = n
return 1