11727

날짜 : 2022. 11. 23

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())
a = [0] * 1001
a[1] = 1
for i in range(2, len(a)): a[i] = a[i-1] * 2 + (-1)**i
print(a[n]%10007)

 

 

풀이

- 직사각형 길이에 따른 개수를 4까지 구한다면 다음과 같다

a[1] = 1, a[2] = 3, a[3] = 5, a[4] = 11 ...

- 해당 경우의 수를 통해 a[i] = a[i-1]*2 + (-1)**2 (n >=2) 라는 점화식을 도출할 수 있었다.

 

 

알게된 점

- 근데 왜 문제를 채점하는데 3분씩이나 걸릴까 모르겠다..

- 다른 풀이를 찾아보니 dp[i] = dp[i-1] + 2 * dp[i-2] 라는 점화식이 나오는데....ㅎㅎ

 

참고 사이트

-