1.
테이블 정의
•
D[i] = 2 x i 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수
2.
점화식 찾기
•
D[n] = D[n - 1] + D[n - 2]
3.
초기값 정하기
•
D[1] = 1
•
D[2] = 2
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] = 2;
for (int i = 2; i <= num; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
System.out.println(arr[num-1]);
}
}
Java
복사
→ 이렇게 했는데 오류가 났다…
→ 다시 읽어보니, 이 문구가 있었다
→ 첫째 줄에 2 x n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다
Python
num = int(input())
arr = [0] * (num + 2)
arr[0] = 1
arr[1] = 2
for i in range(2, num+1):
arr[i] = (arr[i - 1] + arr[i - 2]) % 10007
print(arr[num-1])
Python
복사