[알고리즘] 백준 11727 : 2×n 타일링 2 - S3

2023.05.18 풀이

#1 런타임에러 풀이
import sys
input=sys.stdin.readline

n=int(input())
d=[0]*(n+1)

d[1]=1
d[2]=3
for i in range(3, n+1):
    d[i]=d[i-1]+2*d[i-2]

print(d[n]%10007)

• 점화식은 찾았으나 런타임에러

#2 런타임에러 해결
import sys
input=sys.stdin.readline

n=int(input())
d=[0]*(max(4, n+1))

d[1]=1
d[2]=3
for i in range(3, n+1):
    d[i]=d[i-1]+2*d[i-2]

print(d[n]%10007)

---

다른 풀이

# 10007을 미리 나누고, 나머지를 d에 저장
import sys
input=sys.stdin.readline

n=int(input())
d=[0]*(max(4, n+1))

d[1]=1
d[2]=3
for i in range(3, n+1):
    d[i]=(d[i-1]+2*d[i-2])%10007

print(d[n])

n=int(input())

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

print(w[n]%10007)

---

check point

• DP테이블 길이는 최소 4이상이어야함