[Python] 백준 알고리즘 11726 - 2 x n 타일링

백준 알고리즘 11726 -  2 x n 타일링 

문제 출처 : 11726번: 2 ×n 타일링 (acmicpc.net)

11726번: 2×n 타일링

2 x n 타일링

 

접근

다이나믹 프로그래밍, 즉 동적 계획법을 바탕으로 접근을 해야 하는 문제이다.

n이 늘어나는 경우에 맞춰 점화식을 세우고 그에 맞춰서 코드를 진행하였다. 

점화식에 대해 접근을 해보자. 해당 점화식의 경우 피보나치 수열과 유사한 점화식이 등장한다.

점화식의 경우 본인의 인덱스를 i라고 하자. 그럼 i - 2 와 i - 1의 경우의 수를 합산하면 해당 인덱스의 경우의 수가 나온다.

memo[ i ] = memo [ i  -2 ]  + memo [ i  -1 ]

 

풀이코드

'''
2*n 타일링
메모이제이션 활용, 각각의 인덱스를 2*인덱스로 활용
기존의 자원을 사용하면서 탐색을 진행한다. 따라서 반복문의 경우 n번의 탐색을 하므로
시간복잡도는 O(n)이라고 생각한다.
'''

n = int(input())

memo = [0, 1, 2]

# 처음 2번째까지의 경우를 저장하고 호출한다.
# 따라서 3번부터 진행을 하며 10007로 나눠준 결과값을 저장한다.
for i in range(3, n + 1):
    memo.append((memo[i - 2] + memo[i - 1]) % 10007)

print(memo[n])