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

🔗 문제 링크

BOJ 11727번: 2×n 타일링 2

11727번: 2×n 타일링 2

 

📝 풀이 과정

[백준] 11726번: 2×n 타일링 - JAVA과 이어지는 문제이다.

 

 

노란색으로 체크된 n - 1의 타일에 2x1 타일이 세로로 하나 붙은 형태를 가지고 있고,

파란색으로 체크된 n - 2의 타일에 2x1 타일이 가로로 2개 붙어있거나, 2x2 타일이 붙은 형태를 가지고 있다.

 

이전 문제에서 n - 2의 타일에 붙이는 타일은 2x1타일이 가로로 2개 붙은 형태만 가능했었는데, 타일이 추가되면서 대신 2x2타일도 가능하게 된 것을 알 수 있다.

 

따라서, 점화식은 $dp[n]=dp[n-1]+2\times dp[n-2]$이다.

 

💻 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] dp = new int[1001];
        dp[1] = 1;
        dp[2] = 3;
        for (int i = 3; i <= n; i++)
            dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;

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

 

📊 제출 결과