(python) 백준 알고리즘 11727번 - Dynamic Programming

백준 알고리즘 11727번 2xN 타일링 2

백준 알고리즘의 11727번을 풀어보았다.
혼자서 조금 고민하다가 규칙이 좀 쉬웠는데 어떻게 잘 풀어서 쓸까 고민중이었다.
그런데 고으니양의 '피보나치 수열'을 보는 순간 그냥 코드를 외워버렸다.

DP(dynamic programming)으로 풀었는데 다른 DP들을 풀기 전에 어떻게 접근하면 될지 참고하며 되겠다.

**생각한 방식**

n번째의 count를 구할 때
    - 2x1을 더하는 1가지 경우 > [n-1]까지의 값
    - 2X2를 더하는 2가지 경우 (2x2 한 개 or 1x2 두 개[) > [n-2]까지의 값 x2

이 두 경우의 수를 더한(+)값이 찾고자 하는 counting 갯수이다.

코드 (Python v2)

def countBricks(n):
    blist = []
    for i in range(0, n + 1):
        if i == 0 or i == 1:
             blist.append(1)
        else:
            blist.append((blist[i - 1] + blist[i - 2] * 2) % 10007)
       
    return blist[n] % 10007
 
 
n = input()
print countBricks(n)