[백준 11727] 2×n 타일링 2

🍎 [백준 11727] 2×n 타일링 2

 

문제링크

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

 

⚾ 코드

n = int(input())

dp = [0]*(n+1)

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

print(dp[n])

 

🔔 해결 과정 & 깨달은 점

 

- 다음은 내가 문제를 풀면서 생각한 아이디어 이다.

 

- 각 N은 (이전(N-1)의 경우의 수 + 2*1 타일 추가한 것) + (전전(N-2)의 경우의 수 + 2*2 타일 또는 2*1 타일 2개 추가한 것) 으로 이루어져 있다.

- 새로 추가하는 타일 이외의 경우의 수는 이전의 N의 경우의 수에 포함되어 있기 때문에 따로 생각하지 않아도 된다.

 

- 처음에 dp = [0]*(n+1) 이라고 코드를 작성했을 때 런타임 에러가 났다. 이를 dp = [0]*1001로 바꾸어 주니 바로 통과되었다. n의 범위가 주어졌을 때는 DP 테이블을 초기화 할 때 숫자로 입력해 주는 것이 좋을 것 같다.