[백준] 11727 2*n 타일링2 / 실3 / DP

이거 문제가 왜 익숙한가 했는데

이.취.코 파이썬 책 DP 챕터- 바닥공사랑 똑같은 문제였음

 

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

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

print(dp[n])

 

dp의 각 칸이 타일의 가로 1칸이라고 생각한다 (세로는 어차피 2로 고정)

 

가로 길이가 1일때는이거 문제가 왜 익숙한가 했는데

 

이.취.코 파이썬 책 DP 챕터- 바닥공사랑 똑같은 문제였음

 

 

dp의 각 칸이 타일의 가로 1칸이라고 생각한다 (세로는 어차피 2로 고정)

 

가로 길이가 1일때는 1*2밖에 못넣으니까 1

 

가로 길이가 2일 때는 1*2 타일 2개 또는 2*2 타일 1개, 또는 2*1 타일 2개로 시작할 수 있음

 

그 다음부터는 

i-1 번째 요소를 살펴서 i-1번째에서 길이가 1 늘어나서 1*2 타일을 한 개 더 배치한다고 생각하거나

i-2 번째 요소를 살펴서 i-2 번째에서 길이가 2 늘어나서 2*2 타일 또는 2*1타일 두개를 더 배치한다고 생각하면 됨

 

그래서 i-1번째 1가지 + i-2번째*2가지를 계산해서 i번째에 넣어주면 됨

 

결과적으로 n번째 값을 return하면 된다

 

문제 조건에서 10007로 나눈 나머지 넣으라고 했으니까 계산식값%10007 해서 넣으면 댐