BOJ_11727_2xN타일링2_JAVA
문제 : 2xN타일링2
링크 : BOJ_11727_2xN타일링2
접근 방식
2xN 타일링에 이어서 생각해볼 수 있다.
2xN 타일링에서, 큰 사각형이 추가되었다는 뜻은, 세로로 2개, 가로로 2개 이어져있는 타일을 큰 사각형으로 바꿔치기 할 수 있다는 뜻이다.
N-1은 한 개의 타일이 들어갈 공간이 추가될 경우,
N-2는 두 개의 타일이 들어갈 공간이 추가될 경우를 뜻한다. 2x2의 큰 사각형이 들어갈 수 있느 경우는 N-2의 경우이므로, dp[N-1] + dp[N-2]*2를 구해주면 된다.
다른 관점으로는 이러한 것도 있다.
2개의 블럭이 들어갈 수 있는 공간에는, 1개의 타일을 2개 놓는 방법과 2x2 타일 1개를 놓는 방법 2가지의 경우의 수로 나뉠 수 있다 그렇기 때문에 dp[N-2] 구간에서 * 2를 해준다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BOJ_11727_2xN타일링2 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(in.readLine());
int dp[] = new int[N];
if (N == 1) {
System.out.println(1);
return;
}
dp[0] = 1;
dp[1] = 3;
for(int i=2;i<N;i++) {
// if(i%2 == 0) {
// dp[i] = dp[i-1] + dp[i-2]*2;
// }else {
// dp[i] = dp[i-1]*2 + dp[i-2];
// }
dp[i] = (dp[i-1] + dp[i-2]*2)%10007;
}
System.out.println(dp[N-1]);
}
}