[코딩테스트] 백준 11726번: 2×n 타일링

1. 아이디어

▪ DP 알고리즘 사용

▪ A(n) = A(n-1) + A(n-2)

   - 타일 크기가 1일 때: 1가지

   - 타일 크기가 2일 때: 2가지

   - 타일 크기가 3일 때: 3가지

▪ 타일 크기에 해당하는 방법의 수 초기 배열 만들기 -> [0,1,2]

▪ 3부터 n까지 for 문 돌면서 이전값과 전전값 더하고 %10007하고 append

▪ 배열의 n번째 값 출력

2. 시간복잡도

▪ O(N)

3. 변수

▪ 타일 크기 별 방법의 수 배열: int[]

Code

import sys
input = sys.stdin.readline

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])

 

11726번: 2×n 타일링