https://www.acmicpc.net/problem/11726

2*n 길이의 타일을 만드는 경우의 수를 구하는 문제이다.

n길이의 타일은 이전 n-1 또는 n-2 길이의 타일에 타일을 하나 추가해서 만드는 것과 같은 것을 직관으로 알 수 있다.

따라서 이전 값을 저장해서 활용하는 dp를 사용하여 문제를 해결하였다. dp를 풀때는 이전값과의 관계를 파악하는 것이 중요하다.

변수 dp[i] = k, i길이의 타일을 만드는 경우의 수가 k라는 뜻이다. 이 변수를 1부터 차례대로 구하여 dp[n]을 구하면 되는 문제로 바뀌게 된다.

Fail 풀이

dp[1] = 1, dp[2] =2
dp[i] = dp[i-1] + dp[i-2] * 2

dp[i-1], i-1길이의 타일에 세로로 세운 타일 하나를 붙이는 경우의수
dp[i-2], i-2길이의 타일을 만드는 방법에서 가로 눕힌 타일을 두개 붙이거나 세로로 세운 타일을 두개를 붙이거나 해서 2가지 경우의 수를 곱했다.

fail 이유는 두 덧셈사이에 교집합이 존재하기 때문이다.

편의상 세로로 세운 타일을 1, 가로로 눕힌 타일을 0으로 표시하겠다.

dp[4]를 만드는 방법은
0000 0011 0110 1100 1111 총 5가지이다. 위 fail 풀이대로 구하게되면

dp[3] : 111 001 100 + 1 => 1111 0011 1001 -> 3가지이다.
dp[2] : 00 11 + 00 or 11 => 0000 0011 1100 1111 -> 4가지이다.

즉, 0011과 1111이 겹치게 된다.

다시 생각해보면 dp[i-2] 에서 11을 더하는 방식은 dp[i-1]에서 1을 더하는 방식에 포함되게 된다.

correct 풀이

따라서 dp[i] = d[i-1] + dp[i-2] 이다.

n = int(input())

dp = [0]*(n+1)

dp[1]=1
dp[2]=2

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

for i in dp:
    print(i, end=' ')

주의사항

dp를 미리 선언할때 조심해야 하는것이 있다.
인덱스 0을 사용하지 않기떄문에 n+1개를 선언해줘야한다. 또한 초기값을 많이 설정해주는 문제의 경우 (dp[3] =...) n+3 처럼 개수를 늘려줘야 런타임에러가 뜨지 않는다.