[백준] 11727 - 2*n 타일링 2 (동적프로그래밍) - (python 파이썬)

문제링크 : https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

풀이과정:

앞선 문제인 11726 - 2*n 타일링 1번 보다는 점화식을 구하는데 시간이 걸린 문제였지만,

그렇게 어렵지 않게 점솨히슥을 구할 수 있었다.

n = 1 일때, 1

n = 2 일때, 3

n = 3 일때, 5

n = 4 일때, 11

n = 5 일때, 21

n = 6 일때, 43

이까지 구해보았고, 이를 통해 dp[n] = dn[n-2]*2 + dp[n] 이라는 점화식을 구할 수 있다.

n = int(input())
dp = [None, 1, 3]
for i in range(3, 1001):
    dp.append(dp[i-2]*2 + dp[i-1])
print(dp[n])

 

답(이미지)

 

 

후기 : 커지는 속도가 상당히 빠른거같아 n에 900을 대입하여 값을 구해보았더니, 세상에...

자릿수를 셀수도 없을정도로 큰 수가 나온다... 역시 컴퓨터는 대단하다..