파이썬 알고리즘
[파이썬] 백준 7113 Rectangle
뜻 지, 깨달음 오
2022. 10. 25. 17:10
https://www.acmicpc.net/problem/7113
7113번: Rectangle
Vilibald has decided to cut a right-angled checked page of size n×m cells into squares. First of all he cut off the largest possible square using a straight cut. Then he took away the square and repeated the action with the remaining rectangle. In this wa
www.acmicpc.net
3 7
정사각형을 자르는 프로세스를 숫자로 나타내면
n m
3 7
3 4
3 1
2 1
1 1이다
즉, 둘중에 높은 값에서 낮은 값을 빼기를 반복하다가,
n==m일 때 재귀를 멈추면 된다.
그리고 import를 통해
recursionlimit을 높혀주었다.
전체 코드)
import sys
sys.setrecursionlimit(10**7)
N, M = map(int, input().split())
cnt = 0
def rcr(n, m):
global cnt
if n==m:
cnt +=1
return
if n>m:
cnt+=1
rcr(n-m, m)
elif m>n:
cnt+=1
rcr(n, m-n)
rcr(N, M)
print(cnt)