1.
테이블 정의
•
D[i] → 2 x n 직사각형을 1 x 2, 2 x 1, 2 x 2 타일로 채우는 방법의 수
2.
점화식 찾기
•
D[i] = D[i - 1] + (2 x D[i - 2])
3.
초기값 설정
•
D[1] = 1
•
D[2] = 3
Python
num = int(input())
arr = [0] * (num + 2)
arr[0] = 1
arr[1] = 3
for i in range(2, num+1):
arr[i] = (arr[i - 1] + (2 * arr[i - 2])) % 10007
print(arr[num-1])
Python
복사
JAVA
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] arr = new int[num + 2];
arr[0] = 1;
arr[1] = 3;
for (int i = 2; i <= num; i++) {
arr[i] = (arr[i - 1] + (2 * arr[i - 2])) % 10007;
}
System.out.println(arr[num-1]);
}
}
Java
복사