BOJ 11727. 2×n 타일링 2 - JAVA

https://www.acmicpc.net/problem/11727

 

🥕 아이디어

 

DP 문제에 약한 저는 N이 1일 때 부터 6일 때 까지 손수 그려보며 규칙을 찾고자 노력했습니다.

 

N이 5일 때 `2 + 3` 타일로 나누어 생각했습니다.

그리고 `중간에 겹치는 부분`에 들어갈 2*1 타일과 2*2타일을 생각했습니다.

그렇게 나온 점화식은 `D[i] = 3 * D[i - 2] + 2 * D[i - 3]` 입니다.

 

다른 분들의 풀이를 보니 1 + 4 타일로 나누어 생각했던데, 점화식은 다르게 나오더라도 결국 같은 접근법입니다.

 

 

제출 코드

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] D = new int[1001];

		D[1] = 1;
		D[2] = 3;
		D[3] = 5;
		for (int i = 4; i <= n; i++) {
			D[i] = (3 * D[i - 2] + 2 * D[i - 3]) % 10007;
		}
		System.out.println(D[n]);
	}
}

 

효율성