백준 11727 자바 - 2*n 타일링2

문제

---

 

 

 

문제해결

---

- 1*2 와 2*1의 타일로만 채우는 문제에서는

dp[i-1] 에 세로 타일 하나 추가한 경우의 수

+

dp[i-2] 에 가로 타일 두개 추가한 경우의 수를 구하면 되었다

 

- 이 문제의 경우 2*2 타일이 있으므로

dp[i-1] 에 세로 타일 하나 추가한 경우의 수

+

dp[i-2] 에 가로 타일 두개 추가한 경우의 수

+

dp[i-2]에 2*2 타일 하나 추가한 경우의 수

- dp[i] = dp[i-1] + dp[i-2] + dp[i-2]

- dp[i] = dp[i-1] + dp[i-2] * 2

- 피보나치 수열 구하는 방법이랑 똑같이 하되 점화식만 바꿔주면 된다

import java.util.Scanner;
//dp[i] = dp[i-1] + dp[i-2] * 2
public class B11727 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2] * 2;
            dp[i] %= 10007;
        }
        System.out.println(dp[n]);
    }
}