[python] 백준 11726번 2 X n 타일링 문제 풀이

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

 

 

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

 

 

 

 

 

---

 

💻 코드

 

방법 1)

BottomUp 방식 : 반복문 사용

 

import sys

d = [0] * 10001

def RectangleCount(x):
    d[1] = 1
    d[2] = 2

    for i in range(3, x + 1):
        d[i] = d[i - 1] + d[i - 2]

    return d[x]


n = int(sys.stdin.readline())

print(RectangleCount(n) % 10007)

 

 

 

 

방법 2)

TopDown 방식 : 재귀 함수 사용

 

import sys

d = [0] * 10001

def RectangleCount(x):
    d[1] = 1
    d[2] = 2

    for i in range(3, x + 1):
        d[i] = d[i - 1] + d[i - 2]

    return d[x]


n = int(sys.stdin.readline())

print(RectangleCount(n) % 10007)

 

 

 

 

 

📝 풀이

 

이 문제는 풀이 과정을 생각해내는 데에 오래 걸렸던 문제이다. n이 1일 경우부터 6일 경우까지의 경우의 수를 그려서 규칙을 찾아내었다. 이 규칙을 찾아내는 과정이 막혔던 부분이었는데 여러 가지 방법을 시도함으로써 해결할 수 있었다.

 

 

n이 1일 경우부터 n이 6일 경우의 수를 그림으로 그린 것이다.

 

 

이렇게 그림으로 그린 다음 체계적으로 박스가 어떻게 만들어지는지 살펴보니까 쉽게 풀렸었다. (처음에 너무 복잡하게 생각했던 것 같다. 이 문제를 풀면서 깨달은 것은 규칙을 찾을 때 체계적으로 봐야 한다는 것이다.)

 

 

 

1. 규칙 찾기

그림에서 볼 수 있듯이 n이 3일 때, n - 1 부분에 선을 그으면 n이 2일 때 경우의 수가 들어있고 n - 2 부분에 선을 그으면 n이 1일 때 경우의 수가 들어있다. n이 4일 때, n - 1 부분에 선을 그으면 n이 3일 때 경우의 수가 들어있고 n - 2 부분에 선을 그으면 n이 2일 때 경우의 수가 들어있다. 이와 같이 n이 커졌을 경우에도 이것이 반복됨을 알 수 있다.

 

2. 어떤 방법으로 풀어야할지(알고리즘) 생각해보기

처음에는 부분 문제들이 재귀적으로 반복된다고 생각하여 다이나믹 프로그래밍 문제라고 생각했고 재귀 함수를 만들어서 풀었다.

 

작성한 코드는 다음과 같다.

 

import sys

d = [0] * 1000


def RectangleCount(x):
    if x == 1:
        return 1

    if x == 2:
        return 2

    if d[x] != 0:
        return d[x]

    d[x] = RectangleCount(x - 1) + RectangleCount(x - 2)

    return d[x]


n = int(sys.stdin.readline())

print(RectangleCount(n) % 10007)

 

 

그런데 채점을 해보니 런타임 에러가 발생하였다. 그래서 다시 테스트를 해보았더니 999까지는 정상적으로 작동하였는데 1000을 입력하니까 에러가 났었다. 

 

RecursionError: maximum recursion depth exceeded in comparison

 

이 에러는 재귀와 관련된 에러이다. 이 에러는 python이 정한 최대 깊이보다 재귀의 깊이가 더 깊기 때문에 발생한다. 이를 해결하는 방법은 두 가지 방법이 있다.

 

 

첫 번째) 재귀 함수를 쓰지 않는 방법 (반복문 사용)

 

이 문제는 다이나믹 프로그래밍의 BottomUp 방식으로 반복문을 사용해서도 풀 수 있다.

 

반복문을 사용한 풀이는 코드 방법 1)에서 확인할 수 있다.

 

 

두 번째) python이 정한 최대 재귀 깊이를 변경하는 방법

sys.setrecursionlimit() 함수를 사용하면 최대 재귀 깊이를 변경할 수 있다.

 

sys.setrecursionlimit(10**4)

 

와 같이 입력하면 최대 재귀 깊이를 10,000 정도로 크게 설정할 수 있어 런타임 에러 없이 실행된다.

 

 재귀 함수를 사용한 풀이는 코드 방법 2)에서 확인할 수 있다.

 

 

 

---

 

※ 참고

 

https://help.acmicpc.net/judge/rte/RecursionError

런타임 에러 (RecursionError)