[파이썬]백준 2630 색종이만들기

링크

백준 2630 색종이만들기

분할정복 문제를 풀어보았다.
색종이를 자르기 위해 사분트리(Quad Tree)를 만들어서 풀면된다.

처음에는 슬라이싱을 사용해 실제로 리스트를 잘라가며 인자로 넘겨주려 했지만 그렇게 하니 종이내에서 같은것과 다른것을 비교하기가 난감했다.

그래서 함수의 인자로 좌상단의 좌표값을 넘겨주고 거기서부터의 길이를 계산하는 식으로 구현했다.

정답 코드

def fib(n):
    if n == 0 or n == 1:
        memo[n] = n
        return n
    elif memo[n] == 0:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

for _ in range(int(input())):

    memo = [0] * 41
    n = int(input())
    if n == 0:
        print('1 0')
    else:
        fib(n)
        print(memo[n-1], memo[n])

알게된 것👨‍💻

• 재귀재귀재귀재귀