[BOJ_11726] 2xn 타일링

그림을 그려가면서 가로의 길이에 대해 몇 가지의 방법으로 타일링을 할 수 있는지 구해봅시다

 

가로의 길이	1	2	3	4
방법의 수	1	2	3	5

점화식이 피보나치 수열처럼 이루어지는 것을 알 수 있습니다.

f(n) = f(n-2) + f(n-1) (n>2)

 

위의 테이블대로 dp테이블을 구현해준다는 생각으로 코드를 짜겠습니다.

 

n = int(input())
dp = [0 for _ in range(1001)]

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

print(dp[n]%10007);

조금만 잘못 짜면 IndexError가 발생할 수 있으니 주의해야합니다.

결과로 특정 수와 나눈 나머지를 출력하라고 요구하는 이유는 결과값이 굉장히 커질 수 있기 때문에 그런 것입니다.

그런데, 이 문제는 채점 시간이 굉장히 기네요;... 3~4 분 걸린 것 같습니다.

 

www.acmicpc.net/problem/11726

11726번: 2×n 타일링