n = int(input()) dp = [0] * 1001 dp[1] = 1 dp[2] = 2 for i in range(3, 1001): dp[i] = dp[i-2] + dp[i-1] print(dp[n] % 10007) 처음에는 너무 복잡하게 생각했다. 그냥 간단하게 수열의 점화식을 찾고, 그 값들을 리스트에 저장하는 메모이제이션 방법을 사용해 풀면 되는 것이었다. 나열되는 방법의 수들의 규칙성을 찾고 그것을 점화식으로 표현하면 다음과 같다. dp[i] = dp[i-2] + dp[i-1] 이 점화식을 이용해 리스트에 값들을 메모이제이션하기에 앞서 2x1 크기의 직사각형을 채우는 방법의 수는 1, 2x2 크기의 직사각형을 채우는 방법의 수는 2이므로 dp[1], dp[2]에 각각 1과 2를 먼저 넣는다..
