[伯俊]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)