[백준] 11727번 : 2×n 타일링 2

문제

 

 

접근 방식

11726번 문제에서 2*2 타일의 경우가 추가된 문제다.

 

i번째에 놓을 수 있는 경우가 기존 문제에서는 DP[i-1] + DP[i-2] 였다면

이번 문제에서는 DP[i-2]를 한 번 더 더해주면 된다.

 

DP[i-2]를 한 번 더 더해주는 이유는 이전 문제 설명글에서 설명한거처럼

1*2 타일을 놓는 경우는 나머지 한층도 1*2 타일을 놓을 수 밖에 없어

사실상 2*2타일을 놓는 경우와 같기 때문에

해당 경우를 한 번 더 계산해 주기만 하면 된다.

 

따라서 DP 테이블의 초기값은 기존 문제의 테이블에서

2번째 경우에 한 가지를 더 추가해서 DP[1] = 1, DP[2] = 3이 되고

이 테이블을 기준으로 계산해주면 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		if (n == 1) {
			System.out.println(1);
			return;
		}

		int[] dp = new int[n + 1];

		dp[1] = 1;
		dp[2] = 3;

		for (int i = 3; i <= n; i++) {
			dp[i] = (dp[i-1] + dp[i-2] + dp[i-2]) % 10007;
		}

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