[BOJ 11727] 2xn 타일링 2 (java)

문제 링크 https://www.acmicpc.net/problem/11727

기존의 2xn 타일링 문제에서 2x2 타일을 오른쪽에 미리 채우고 시작한다는 조건만 붙었기 때문에 n-2를 더해주면 된다.

1) Top-down 풀이

package basics_400;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ11727 {
	//memo[n] = 2x크기의 직사각형을 채우는 방법의 수 
	static int[] memo;
	static int makeTile(int n) {
		//2x0 크기의 직사각형을 채우는 방법의 수는 0개지만 이것도 1가지 
		//2x1 크기의 직사각형을 채우는 방법의 수 는 1가지 
		if(n==0||n==1)
			return 1;
		
		//답을 이미 구한 경우 
		if(memo[n]>0)
			return memo[n];
		
		//결과 계산 
		memo[n] = makeTile(n-1)+makeTile(n-2)+makeTile(n-2);
		memo[n] %= 10007;
			
		return memo[n];
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		memo = new int[n+1];

		System.out.println(makeTile(n));
	}

}

2) Bottom-up 풀이

package basics_400;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ11727_2 {
	//memo[n] = 2x크기의 직사각형을 채우는 방법의 수 
	static int[] memo;
	static int makeTile(int n) {
		//2x0 크기의 직사각형을 채우는 방법의 수는 0개지만 이것도 1가지로 침 
		memo[0] = 1;
		//2x1 크기의 직사각형을 채우는 방법의 수 는 1가지 
		memo[1] = 1;
		
		for(int i=2;i<=n;i++) {
			//memo[n]을 계산
			//memo[n-1] = 2xn 타일의 가장 오른쪽에 1x2를 채우고 나머지를 계산
			//memo[n-2] = 2xn 타일의 가장 오른쪽에 2x1을 채우고 나머지를 계산 		
			memo[i] = memo[i-1]+memo[i-2]+memo[i-2];
			memo[i] %= 10007;
		}	
		return memo[n];
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		memo = new int[n+1];

		System.out.println(makeTile(n));
	}

}