자료구조와 알고리즘/문제풀기
백준 11727 - 2 X N 타일링 2
now0204
2023. 4. 14. 10:58
2*n타일링 문제에서 채울 수 있는 타일 2*2가 추가 된 것이다.
이제 2*2 타일은 2*1과 1*2와 2*2타일로 채울 수 있다. 3가지 타일로
다른 2*n타일로 마찬가지로 n-1타일에 2*1타일 추가 n-2타일에 1*2위아래 추가 n-2타일에 2*2타일 추가의 경우의 수로
2*n타일을 채우는 경우의 수를 생각할 수 있으니
점화식은
D[n] = D[n-1]+D[n-2]+D[n-2]이다.
상태:N , 종료조건 : 0일때는 0 1일때 1개 2일때 3개 return
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static int[] d;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
d = new int[n+1];
d[1]=1;
System.out.print(two_n(n));
}
public static int two_n(int n){
if(n == 0) return 0;
if(n == 2) return 3;
if(d[n] > 0) return d[n];
d[n] = two_n(n-1) + two_n(n-2) + two_n(n-2);
d[n] %= 10007;
return d[n];
}
}