일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 분할정복
- 영어
- 백준
- Spring Security
- python
- codility
- github
- caniuse
- 신규아이디추천
- 1793번
- 입이 트이는 영어
- 프로그래머스
- 11727번
- 11047번
- 1992번
- 18406번
- WebSecurityConfigurerAdapter
- 2630번
- EBS어학당
- 1057번
- 1759번
- SecurityFilterChain
- 파이썬
- 2163번
- 알고리즘
- BinaryGap
- 9251번
- programmers
- Java
- 권주현의 진짜 영국 영어
Archives
- Today
- Total
철갑이의 이모저모
[백준] 11727번(2xn 타일링 2) with Python 본문
728x90
문제
풀이
dp문제는 처음 풀어봐서 하나하나 그려서 규칙을 찾은 후 점화식을 구했다.
위의 그림과 같이 N이 3 이상 이면
N-1에서 2x1 타일이 붙고, N-2에서 1x2 타일 두 개, 2x2 타일이 한 개 붙는 규칙이 계속된다.
따라서, dp[n] = dp[n - 1] + dp[n - 2] * 2
dp[1]과 dp[2]를 미리 구해서 시작.
답
a = int(input())
dp = [0,1,3]
for i in range(3, a + 1) :
dp.append(dp[i - 1] + dp[i - 2] * 2)
print(dp[a] % 10007)
728x90
'알고리즘' 카테고리의 다른 글
[백준] 1759번(암호 만들기) with Python (0) | 2020.10.13 |
---|---|
[백준] 1793번(타일링) with Python (0) | 2020.10.08 |
[백준] 2003번(수들의 합 2) with Python (2) | 2020.10.02 |
[백준] 18406번(럭키 스트레이트) with Python (0) | 2020.10.02 |
[백준] 1057번(토너먼트) with Java (0) | 2020.09.27 |