[BaekJoon] 11726번 2×n 타일링 (Silver 3) - Python

문제

 

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

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

예

---

입출력 예시

 

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

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

---

코드

a = int(input()) # 입력 받는다

result = [0 for _ in range(0, 1001)] # 1000의 길이를 갖는 리스트를 미리 선언한다.
result[1] = 1 # n = 1일때의 경우의수는 1
result[2] = 2 # n = 2일때의 경우의수는 2
for i in range(3, 1001): # n = 3부터 n = 1000까지 모든 경우의수를 미리 계산해놓는다.
    result[i] = (result[i - 1] + result[i - 2]) % 10007 # 괄호 안은 점화식 result[n - 1] + result[n - 2]
    # n = 1일 때 1
    # n = 2일 때 2
    # n = 3일 때 3
    # n = 4일 때 5
    # n = 5일 때 8
    # .
    # .
    # .
    # n = n일 때 n - 1의 경우의수 + n - 2의 경우의수 => 점화식

print(result[a]) # a일때의 경우의수 출력

---

실행 화면

실행 화면

---

채점 결과

처음에 재귀함수로 풀어서 시간초과가 진짜 많이 떴는데, 반복문으로 하니까 빠르드라 ㅇ.ㅇ