백준 11726번 2xn 타일링

전형적인 다이나믹 프로그래밍 문제이다.

1x2, 2x1의 타일을 가지고 2xn의 타일을 채우는 경우의 수를 구하는 문제이다.

n=1부터 그림을 그려가며 갯수를 세어나가면 쉽게 규칙을 찾을 수 있다.

 

n=1 -> 1가지

n=2 -> 2가지

n=3 -> 3가지

위의 모양을 보면 n=3인 경우, 1과 2의 모양들의 결합으로 이루어지는것을 볼 수 있다.

조금 더 정확한 확인을 위해 n=4,5인 경우까지 확인해보면 다음과 같은 규칙성을 찾을 수 있다

DP[n] = DP[n-1]+DP[n-2]

 

이를 코딩으로 나타내면 다음과 같다. (10007로 나눈 나머지로 표시해주어야 한다)

n = int(input())
 
dp = [0, 1, 2]
 
for i in range(3, n+1):
    dp.append( (dp[i-1] + dp[i-2]) % 10007)
 
print(dp[n])