11726 / 11727

2xn 타일링

 

따져보면..

dp[1] =1

dp[2] =2

dp[3] = dp[2] + dp[1]

...

 

dp[5] = dp[4] + dp[3]

타일을 l 모양으로 배치하는 경우 : dp[4]

타일을 = 모양으로 배치하는 경우 : dp[3] 

(경우의 수를 생각할 때, 중복이 없도록 선택해야 한다.)

 

조건에 % 10007 모듈로 연산이 있는 이유는 2^n이 Integer.MAX_VALUE를 초과하기 때문

import java.util.Scanner;

class Main {
	static int n;

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int [] dp = new int[1001];
		dp[1] = 1;
		dp[2] = 2;
		for (int i = 3; i < 1001; ++i)
			dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;

		System.out.println(dp[n]);
	}
}
ex)
input
1000
output
1 1
2 2
3 3
4 5
5 8
6 13
7 21
8 34
9 55
10 89
11 144
12 233
13 377
14 610
15 987
16 1597
17 2584
18 4181
19 6765
...

992 8863
993 5050
994 3906
995 8956
996 2855
997 1804
998 4659
999 6463
1000 1115

 

 

 

2xn 타일링 2

 

2x2 모양의 타일이 추가 된 것 외에는 동일.

 

따져보면..

dp[1] =1

dp[2] =3

dp[3] = dp[2] + dp[1]*2

...

 

dp[5] = dp[4] + dp[3]*2

타일을 l 모양으로 배치하는 경우 : dp[4]

타일을 = 모양으로 배치하는 경우 : dp[3] 

2x2 타일을 ㅁ 모양으로 배치하는 경우 : dp[3] 

(경우의 수를 생각할 때, 중복이 없도록 선택해야 한다.)

 

import java.util.Scanner;

class Main {
	static int n;

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int[] dp = new int[1001];
		dp[1] = 1;
		dp[2] = 3;
		for (int i = 3; i < 1001; ++i)
			dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;

		System.out.println(dp[n]);

	}

}