목록점화식 (1)

하나씩 알아가기

[BOJ_11727] 2xn 타일링 2

점화식을 찾아봅시다. 그림을 보고 입력받은 수가 n이라 할 때, n-2번째 까지의 경우는 두 가지이고 n-1번째 까지의 경우는 한 가지입니다. 좀 더 자세히 말하면 n-2번째까지 타일이 채워진 경우에서 너비가 2인 블럭으로 채우면 n번째 항까지 채운 경우가 되고 n-1번째 까지 타일이 채워진 경우에서 너비가 1인 블럭으로 채우면 n번째 항까지 채운 경우가 되는 것입니다. 그래서 f(n) = 2 * f(n-2) + f(n-1) 이렇게 점화식을 구할 수 있습니다. n = int(input()) dp = [0 for _ in range(1001)] dp[0] = 0 dp[1] = 1 dp[2] = 3 for i in range(3, n+1): dp[i] = 2 * dp[i-2] + dp[i-1] print(d..
알고리즘 2021. 1. 22. 19:38
이전 Prev 1 Next 다음