 |
|
" 문제 "
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 |
" 참고자료 "
반응형
'알고리즘 > Baekjoon' 카테고리의 다른 글
| [ Baekjoon : python ] 백준 9095번 1, 2, 3 더하기 - 다이나믹프로그래밍 (0) | 2021.02.20 |
|---|---|
| [ Baekjoon : python ] 백준 11727 2×n 타일링 2 - 다이나믹프로그래밍 (0) | 2021.02.20 |
| [ Baekjoon : python ] 백준 2021 1로 만들기 - 다이나믹 프로그래밍 (재귀호출) (0) | 2021.02.20 |
| [ Baekjoon : python ] 백준 3085 사탕게임 - 브루트포스 (0) | 2021.02.20 |
| [ Baekjoon : python ] 백준 10866 덱 Deck - 파이썬으로 덱 구현하기 (0) | 2021.01.03 |
