[백준(BOJ)] 11727번 : 2xn 타일링 2 - PYTHON[파이썬]

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

11727번: 2×n 타일링 2

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 다이나믹 프로그래밍

 

---

 

⊙ 문제 접근 과정

 

규칙을 찾고 점화식을 세우자!

 

N=1, 1개

N=2, 3개

N=3, 5개

N=4, 11개

N=5, 21개

 

점화식 = (N-2)*2 + (N-1)

 

---

 

⊙ 문제 풀이

 

arr= [0,1,3]
for i in range(3,1001):
    arr.append(arr[i-2]*2+arr[i-1])

N=int(input())
print(arr[N]%10007)

---

⊙ 결과

 

---

⊙ 마무리

 

 

DP를 만나면 1부터 규칙을 찾을 때까지 직접 대입해보자

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!