[백준] 11727번 - 2*n 타일링 2

 

예전에 풀었던 2*n 타일링과 비슷한 문제이다.

https://ddamdoo.tistory.com/158

[백준] 11726번 - 2*n 타일링

 

 

이 문제 역시 그림을 그려서 점화식을 유추해보았다.

대표사진 삭제

사진 설명을 입력하세요.

파란색으로 표시한 것을 보면 2개로 만들어진 타일에서 한 개씩 추가한 것을 알 수 있고, 빨간색으로 표시한 것을 보면 1개로 만들어진 타일에서 2개로 만들어질 수 있는 것 중 겹치는 것을 제외한 2개가 추가된 것을 알 수 있다. 이것을 통해서 아래와 같은 점화식을 세울 수 있다.

$f(N)=f(N-1)+f(N-2)*2$f(N)=f(N−1)+f(N−2)*2​

이 식을 통해서 dp로 코드를 작성하면 된다.

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

public class p11727 {
	public static long[] ary;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		ary = new long[a + 1];
		ary[1] = 1;
		if (a >= 2) {
			ary[2] = 3;
		}

		System.out.println(dp(a));
	}

	public static long dp(int a) {
		if (ary[a] == 0) {
			ary[a] = (dp(a - 1) + 2 * dp(a - 2)) % 10007;
		}
		return ary[a];
	}
}