[백준] 7113 : Rectangle

문제

가장 큰 정사각형을 자르고 가져간다.
남은 직사각형이 정사각형이 될 때까지 자른다.
구해야 할 것은 잘라서 얻어진 정사각형의 수가 몇 개인지 구하는 것!

재귀가 부족해서 재귀 관련된 문제를 풀어보려고 했다.
나는 재귀를 훈련하려고 푼 거라 재귀를 이용했지만, 다른 사람들의 풀이를 보니 재귀를 사용하지 않고도 푼 것 같다.

풀이

import sys
sys.setrecursionlimit(10**7) # 최대 재귀 한도 에러가 나서 풀어줬음!
g, s = map(int, sys.stdin.readline().split())
count = 0
def sol(g, s):
    global count
    
    if g == s: # 가로와 세로의 길이가 같을 때 재귀 종료!
        count += 1
        return 
    
    a = min(g, s)
    if g > s:
        count += 1
        sol(g-a, s) # 만약 가로가 더길 때 가로에서 a만큼 잘라주기
    
    if g < s:
        count += 1
        sol(g, s-a) # 만약 세로가 더길 때 세로에서 a만큼 잘라주기
    
sol(g, s)
print(count)