[백준] 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)
Author And Source
이 문제에 관하여([백준] 7113 : Rectangle), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@letsbebrave/백준-7113-Rectangle-fgvivkpn저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)