[Python] 백준 #11727- 2xn타일링 2

문제

---

 

11727번: 2×n 타일링 2

코드

---

My answer

n=int(input())
d=[0]*(n+1)
d[1]=1
if(n>=2):
    d[2]=3
    for i in range(3,n+1):
        d[i]=d[i-1]+(2*d[i-2])
print(d[n]%10007)

Another answer

a=b=1
for i in range(int(input())):
	a,b=b,2*a+b
print(a%10007)

 

풀이

---

우선 관계식 자체는 위의 코드처럼 d[i]=d[i-1]+d[i-2]*2가 나오게 된다. 규칙이 나온 이유는 위에 첨부된 사진을 보면 d[i]의 경우 d[i-1]의 경우에서 그냥 2*1짜리 기둥을 옆에 하나 붙이고 가로가 2인 기둥들은 못붙이므로 끝이고, d[i-2]의 경우에서는 가로가 2인 기둥 모양이 총 2가지 종류가 있으므로 그들을 순서를 바꾸는 것까지 생각해서 x2해줘서 더해주면 된다. 잘 이해가 안가는 사람은 사진의 빨간색, 파란색 그림을 잘 보면서 이해해보길 바란다 자세한 풀이는 박연호님의 개발 블로그를 참조하길 .

[알고리즘 문제] 백준11726 - 2xn 타일링