[BOJ] 11727번 2xn 타일링2 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.util.Scanner;

public class Main {
	static int n;
	static int[] dp = new int[1001];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 3;

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

📄 해설

• 맨 처음 접근한 점화식 : 총 3가지의 경우가 있다고 생각해버려서 아래와 같이 접근함
  • dp[i] = (2 * dp[i-2] + dp[i-1] + dp[i-3])
• i-3 은 고려 대상이 아니었음! -> 해결