Algorithm/Solved Problems
[ Baekjoon : python ] 백준 11726 2xn 타일링 - 다이나믹프로그래밍
leecrossun
2021. 2. 20. 19:39
 |
|
" 문제 "
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
" 아이디어 "
D[n] = 주어진 2 * n 직사각형을 채우는 경우의 수
맨 끝 타일을 1 * 2 타일로 채울 경우 -> D[n-2]
맨 끝 타일을 2 * 1 타일로 채울 경우 -> D[n-1]
D[n] = D[n-1] + D[n-2] (n>=3)
D[n] = 1 (n=1)
D[n] = 2 (n=2)
" 코드 "
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
import sys
sys.setrecursionlimit(10000000)
def calc(n):
if n==1: return 1
if n==2: return 2
if m[n] == 0:
m[n] = calc(n-2) + calc(n-1)
return m[n]
n = int(input())
m = [0]*(n+1)
print(calc(n)%10007)
|
cs |
" 참고자료 "
반응형