[백준] 11726번 2xn 타일링

사용 언어 - Python3

문제 -  11726번 2xn 타일링

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

11726번: 2×n 타일링

 

 

정답

피보나치 타일링 - 바텀업 DP

손코딩, 아이큐 테스트, 규칙 찾기 문제

# 규칙이 보여야만 풀수 있는 문제 => 많이 풀다보면 규칙이 보이는 문제이다.
# 피보나치를 그림으로 만든 문제

0,1,1,2,3,5,8

dp[i] = dp[i-2] + dp[i-1]

 

n dp

1  1

2  2

3  3

4  5

5  8

9  55

import sys
input = sys.stdin.readline

n = int(input())
dp = [0]*1001
dp[1] = 1
dp[2] = 2
for i in range(3,n+1):
    dp[i] = (dp[i-2] + dp[i-1])%10007

print(dp[n])

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/11726_2xn%ED%83%80%EC%9D%BC%EB%A7%81.py