[백준 11727번] 2xn 타일링 2- java

문제 설명

1. 2x1, 1x2, 2x2 세가지 타일로 2xn의 타일을 채워야 한다.

2. 채우는 모든 방법을 구하면 됨.

3. 설명할게 더 없다.

풀이 과정

 1. DP로 문제를 풀었다( bottom-up으로 풀었음)

 2. 2x1을 채우는 방법은 1개, 2x2를 채우는 방법은 3개이다(11, 二, ㅁ)

 3. 2x3을 채우려면 2x2타일 뒤에 1짜리 하나를 두는 방법과 2x1타일 뒤에 (ㅁ, 二) 이 오는 두 가지이다.

 주의) 여기서 1 이 모양이 왜 못오냐면 앞의 경우와 무조건 겹칠 수밖에 없다.

예를들어 - 111, 二1, ㅁ1   이 모든 경우를 2x2타일을 구할 때에 사용한다. 2x2타일을 채울 때에 1을 마지막에 썼기 때문에 모든 경우의 수를 사용한 것이다.

 4. 즉 dp[i] = dp[i-1](앞의 타일수 -> 뒤에 2x1타일 하나 붙임...) + dp[i-2]*2(2앞의 타일수 -> 뒤에 二, ㅁ 두개 붙임...) 가 될것이다.

코드

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		long dp[] = new long[n+1];
		
		dp[1] = 1;
        if(n>1) dp[2] = 3; // n을 1을주거나 하는경우도 있음~
		
		for(int i=3; i<n+1; i++) {
			dp[i] = (dp[i-1] + dp[i-2]*2)%10007;	// 참 희한한게 나머지를 답에서 구하면 꼭 틀리고 앞에서 구하면 맞더라...
		}
		
		long ans = dp[n];
		System.out.println(ans);	// 답임ㅇㅇ
	}
}

나 근데 2xn타일링 1은 풀었던가...? 왜 2부터풀었징